# 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 < 21. So P(1) is true.

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

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

Now, k+1

< 2k + 1, by induction hypothesis.

< 2k + 2k

=2 . 2k

=2k+1

So k+1 < 2k+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 < 2n is proved.

 Problem 2: Prove that $2^n 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+x2$\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)x2 = 1+(k+1+1)x+(k+1)x2$\geq$1+(k+1+1)x as (k+1)x2 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)=n2 Solution: Let P(n) denote the statement 1+3+5+7+…+(2n-1)=n2 Base case: Note that 2.1-1=12. 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)= k2

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)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)=nis valid for all natural numbers n.

Share via: