Important Questions of Mathematical Induction

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¹. 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ⁿ 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)ⁿ⁺¹ $\geq$ 1+(n+1)x

Base case:

Note that (1+x)²=1+2x+x² $\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²

= 1+(k+1+1)x+(k+1)x²

$\geq$ 1+(k+1+1)x as (k+1)x² 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)ⁿ⁺¹ $\geq$ 1+(n+1)x is true for all natural numbers n.

 

Problem 6: Prove that 1+3+5+7+…+(2n-1)=n2

Solution:

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

Base case: Note that 2.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. So we have 1+3+5+7+…+(2k-1)= k²

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² +2k+1

= (k+1)²

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² is valid for all natural numbers n.