In this section, we will discuss a few important questions and answers of mathematical induction. For more details of induction, we refer to our page “an introduction to mathematical induction”

Problem 1: Prove that $n<2^n.$ |

Solution:

Let P(n) denote the statement $n<2^n.$

Base case: Note that 1 < 2^{1}. So P(1) is true.

Induction hypothesis: Assume that P(k) is true for some k $\geq$ 1. So we have k < 2^{k}.

Induction step: To show P(k+1) is true.

Now, k+1

< 2^{k} + 1, by induction hypothesis.

< 2^{k} + 2^{k}

=2 . 2^{k}

=2^{k+1}

So k+1 < 2^{k+1}. It means that P(k+1) is true. Thus we have shown that P(k) implies that P(k+1). Hence by mathematical induction, we conclude that P(n) is true for all integers n $\geq$ 1. In other words, n < 2^{n} is proved.

Problem 2: Prove that $2^n<n!$ for $n \geq 4$ |

Solution:

Let P(n) denote the statement $2^n<n!$

(Base case) Put n=4. Note that $2^4=16$ and $4!=24.$ Thus we have $2^4<4!$ and so P(4) is true.

(Induction hypothesis) Assume that P(k) is true for some $k \geq 4$. So we have $2^k<k!.$

(Induction step) To show P(k+1) is true.

Now, $2^{k+1}$

$=2^k . 2$

$<k!+1,$ by induction hypothesis.

$<(k+1)k!$ as $k \geq 1$

$=(k+1)!$

So $2^{k+1}<(k+1)!.$ In other words, P(k+1) is true. Thus we deduce that P(k) implies that P(k+1). Now applying mathematical induction, we conclude that $2^n<n!$ is true for all integers $n \geq 4.$

Problem 3: Prove that $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}$ $=1-\frac{1}{2^n}$ |

Solution:

Let P(n) denote the statement $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}$ $=1-\frac{1}{2^n}$

Base case: Note that $\frac{1}{2}=1-\frac{1}{2}.$ Thus P(n) holds for $n=1$, that is, P(1) is true.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1$. So we have $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}$ $=1-\frac{1}{2^k}$

Induction step: To show P(k+1) is true.

Now, $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}+\frac{1}{2^{k+1}}$

$=(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k})+\frac{1}{2^{k+1}}$

$=1-\dfrac{1}{2^k}+\dfrac{1}{2^{k+1}},$ by induction hypothesis

$=1-\dfrac{2-1}{2^{k+1}}$

$=1-\dfrac{1}{2^{k+1}}$

So P(k+1) is true. This means that if P(k) holds then P(k+1) also holds. Thus by mathematical induction, we have proven that $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}$ $=1-\frac{1}{2^n}$ for all natural numbers n.

Problem 4: Prove that $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\cdots +\frac{1}{n(n+1)}$ $=\frac{n}{n+1}$ for all natural numbers n. |

Solution:

Let P(n) denote the statement $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\cdots +\frac{1}{n(n+1)}$ $=\frac{n}{n+1}$

Base case: Note that $\frac{1}{1.2}=\frac{1}{1(1+1)}.$ Thus P(n) is true for $n=1$, that is, P(1) holds.

Induction hypothesis: Assume that P(k) is true for some $k \geq 1$. This implies that we have $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\cdots +\frac{1}{k(k+1)}$ $=\frac{k}{k+1}$

Induction step: To show P(k+1) is true.

Now, $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\cdots +\frac{1}{k(k+1)}$ $+\frac{1}{(k+1)(k+1+1)}$

$=[\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\cdots +\frac{1}{k(k+1)}]$ $+\frac{1}{(k+1)(k+2)}$

$=\dfrac{k}{k+1}$ $+\dfrac{1}{(k+1)(k+2)},$ by induction hypothesis.

$=\dfrac{k(k+2)+1}{(k+1)(k+2)}$

$=\dfrac{k^2+2k+1}{(k+1)(k+2)}$

$=\dfrac{(k+1)^2}{(k+1)(k+2)}$

$=\dfrac{k+1}{k+2}$ $=\dfrac{k+1}{k+1+1}$

So P(k+1) is true. It follows that P(k) implies P(k+1). Thus by mathematical induction, $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\cdots +\frac{1}{n(n+1)}$ $=\frac{n}{n+1}$ for all natural numbers n.

Problem 5: For x >-1, prove that (1+x)^{n+1} $\geq$ 1+(n+1)x for all natural numbers n. |

Solution:

Let P(n) denote the statement (1+x)^{n+1} $\geq$ 1+(n+1)x

Base case:

Note that (1+x)^{2}=1+2x+x^{2} $\geq$ 1+2x. Thus P(n) is true for n=1, that is, P(1) holds.

Induction hypothesis:

Assume that P(k) is true for some k $\geq$ 1. So we have (1+x)^{k}^{+1} $\geq$ 1+(k+1)x

Induction step:

To show P(k+1) is true.

Now, (1+x)^{k+1}^{+1}

= (1+x)^{k+1 }. (1+x)

$\geq$ [1+(k+1)x] . (1+x)

$\geq$ 1+(k+1)x+x+(k+1)x^{2}

= 1+(k+1+1)x+(k+1)x^{2}

$\geq$ 1+(k+1+1)x as (k+1)x^{2 }is always positive.

So P(k+1) is true. Therefore we have shown that P(k) implies that P(k+1). Thus by mathematical induction, (1+x)^{n+1} $\geq$ 1+(n+1)x is true for all natural numbers n.

Problem 6: Prove that 1+3+5+7+…+(2n-1)=n^{2} |

Solution:

Let P(n) denote the statement 1+3+5+7+…+(2n-1)=n^{2}

Base case: Note that 2.1-1=1^{2}. Thus P(n) is true for n=1, that is, P(1) holds.

Induction hypothesis: Assume that P(k) is true for some k $\geq$ 1. So we have 1+3+5+7+…+(2k-1)= k^{2}

Induction step:

To show P(k+1) is true.

Now, 1+3+5+7+…+(2k-1)+{2(k+1)-1}

= [1+3+5+…+(2k-1)]+ 2k +2 -1

= k^{2 }+2k+1

= (k+1)^{2}

Thus P(k+1) holds. As a result, we deduce that P(k) implies that P(k+1). Hence by mathematical induction, 1+3+5+7+…+(2n-1)=n^{2 }is valid for all natural numbers n.

This article is written by Dr. T. Mandal, Ph.D in Mathematics. On Mathstoon.com you will find Maths from very basic level to advanced level. Thanks for visiting.