Chapter 4.2 - Solved Examples on Mathematical Induction

In the previous section, we saw problems involving inequalities. In this section we will see some advanced problems.

Solved example 4.1
For all n ≥ 1, prove that:
$\frac{1}{1 × 2}+\frac{1}{2 × 3}+\frac{1}{3 × 4}+\;.\;.\;.\;+\frac{1}{n(n+1)}=\frac{n}{n+1}$
Solution:
1. For all n ≥ 1, let P(n) denote the given statement.
• Then we can write:
$P(n):\,\frac{1}{1 × 2}+\frac{1}{2 × 3}+\frac{1}{3 × 4}+\;.\;.\;.\;+\frac{1}{n(n+1)}=\frac{n}{n+1}$
2. Basic step: (n=1)
$\begin{array}{ll} \phantom{\Rightarrow~}P(1): & \frac{1}{1 × (1+1)} & {}={} & \frac{1}{1+1} \\ {\Rightarrow~} P(1): & \frac{1}{2} & {}={} & \frac{1}{2} \\ \end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
$P(k): \frac{1}{1 × 2}+\frac{1}{2 × 3}+\frac{1}{3 × 4}+\;.\;.\;.\;+\frac{1}{k(k+1)}~=~\frac{k}{k+1}$
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll} \phantom{\Rightarrow~}P(k+1): & \frac{1}{1 × 2}+\frac{1}{2 × 3}+\frac{1}{3 × 4}+\;.\;.\;.\;+\frac{1}{k(k+1)}+\{\frac{1}{(k+1)[(k+1)+1]}\} & {}={} & \frac{k+1}{(k+1)+1} & {} \\ {\Rightarrow~} P(k+1): & \frac{k}{k+1}+\{\frac{1}{(k+1)(k+2)}\} & {}={} & \frac{k+1}{k+2} & {} \\ {}&\color {green}{\text{[Using result in (i)]}} & {}&{} & {} \\ {} & \frac{k(k+2)+1}{(k+1)(k+2)} & {}={} & \frac{k+1}{k+2} & {} \\ {} & \frac{k^2 + 2k +1}{(k+1)(k+2)} & {}={} & \frac{k+1}{k+2} & {} \\ {} & \frac{(k+1)^2}{(k+1)(k+2)} & {}={} & \frac{k+1}{k+2} & {} \\ {}&\color {green}{\text{[Using identity }(a+b)^2=a^2+2ab+b^2]} & {}&{} & {} \\ {} & \frac{k+1}{k+2} & {}={} & \frac{k+1}{k+2} & {} \\ \end{array}$
• So P(k+1) is true.
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for any positive integer n.

Solved example 4.2
For every positive integer n, prove that 7ⁿ - 3ⁿ is divisible by 4.
Solution:
1. For any positive integer n, let P(n) denote the given statement.
• Then we can write:
$P(n):7^n - 3^n \; \text{is divisible by 4}$
2. Basic step: (n=1)
$\begin{array}{ll} P(1): & 7^1 - 3^1 & {} & \color {silver}{\text{is divisible by 4}} & {} \\ {} & 7-3 & {} & {} & {} \\ {} & 4 & {} & \color {silver}{\text{is divisible by 4}} & {} \\ \end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
$\begin{alignat*}{3} P(k)&: 7^k - 3^k &&\text{is divisible by 4} \\ \Rightarrow P(k)&: 7^k - 3^k = 4d &&\;\text{[d is a natural number]} \end{alignat*}$
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll} P(k+1): & 7^{k+1} - 3^{k+1} & {} & {} & {} \\ {} & 7^k  × 7 ~-~3^k × 3 & {} & \color {silver}{\text{is divisible by 4}}~~\color {green}{\text{---- (a)}} & {} \\ {}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\ P(k+1): & (4d+3^k)  × 7 ~-~3^k × 3 & {} & {} & {} \\ {}& {} & {}& \color {green}{\text{[Using the result in (i)]}} & {} \\ {} & 28d~+~7 × 3^k ~-~3^k × 3 & {} & {} & {} \\ {} & 28d~+~3^k(7 ~-~3) & {} & {} & {} \\ {} & 28d~+~3^k  × 4 & {} & {} & {} \\ {} & 4(7d~+~3^k) & {} &  \color {silver}{\text{is indeed divisible by 4}} & {} \\ {}& {} & {}& \color {green}{\text{[d and k are integers]}} & {} \\ {}& {} & {}& \color {green}{\text{[So }(7d~+~3^k)\text{ is an integer]}} & {} \\ \end{array}$
• We proved (a) by rearranging it. The rearrangement was done using P(k)
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for any positive integer n.

Solved example 4.3
Prove that (1+x)ⁿ ≥ (1+nx) for all natural number n, where x > -1.
Solution:
1. For all natural number n, let P(n) denote the given statement.
Then we can write: P(n): (1+x)ⁿ ≥ (1+nx), x > -1
2. Basic step: (n=1)
$\begin{array}{ll} P(1): & (1+x)^1 & {}\ge{} & 1+ 1 × x & {} \\ {} & (1+x) & {}\ge{} & (1+x) & {} \\ \end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
P(k): (1+x)^k ≥ (1+kx)
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll} P(k+1): & (1+x)^{k+1} & {}\ge{} & 1+(k+1)x & {} \\ {} & (1+x)^{k+1} & {}\ge{} & 1+kx+x~\color {green}{\text{---- (a)}} & {} \\ {}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\ {}&{}& {}&{} & {} \\ P(k): & (1+x)^k & {}\ge{} & 1+kx~\color {green}{\text{---- (b)}} & {} \\ {} & (1+x)^k (1+x) & {}\ge{} & (1+kx)(1+x) & {} \\ {}&{}& {}& \color {green}{\text{[Multiplying by (1+x) on both sides]}} & {} \\ {} & (1+x)^{k+1} & {}\ge{} & (1+x+kx+kx^2)~\color {green}{\text{---- (c)}} & {} \\ {}&{}& {}&{} & {} \\ {} & (1+x+kx+kx^2) & {}\ge{} & 1+kx+x~\color {green}{\text{---- (d)}} & {} \\ {}&{} & {}& \color {green}{\text{[Comparing RHS of (b) and (c)]}} & {} \\ {}&{} & {}& \color {green}{\text{[}kx^2~\text{is the only diference]}} & {} \\ {}&{} & {}& \color {green}{\text{[k is a +ve number. Also x is greater than -1]}} & {} \\ {}&{} & {}& \color {green}{\text{[So}~kx^2 \ge 0 \text{]}} & {} \\ {}&{} & {}& \color {green}{\text{[So (d) is true]}} & {} \\ {}&{}& {}&{} & {} \\ {} & (1+x)^{k+1} & {}\ge{} & (1+x+kx+kx^2)~~\ge 1+x+kx~\color {green}{\text{---- (e)}}  & {} \\ {}&{} & {}& \color {green}{\text{[Using (c) and (d)]}} & {} \\ \Rightarrow & (1+x)^{k+1} & {}\ge{} & 1+x+kx & {} \\ {}&{} & {}& \color {green}{\text{[Picking first and last items from (e)]}} & {} \\ {} &{} & {}& \color {green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\ \end{array}$
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for all natural numbers.

Solved example 4.4
For every positive integer n, prove that (5ⁿ - 5) is divisible by 4.
Solution:
1. For any positive integer n, let P(n) denote the given statement.
• Then we can write:
$P(n): 5^n - 5 \; \text{is divisible by 4}$
2. Basic step: (n=1)
$\begin{array}{ll} P(1): & 5^1~-~5 & {} & \color {silver}{\text{is divisible by 4}} & {} \\ {} & 5 - 5 & {} & {} & {} \\ {} & 0 & {} & \color {silver}{\text{is divisible by 4}} & {} \\ \end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
$\begin{alignat*}{3} P(k)&: 5^k ~-~5 &&\text{is divisible by 4} \\ \Rightarrow P(k)&: 5^k ~-~5 = 4d &&\;\text{[d is a natural number]} \end{alignat*}$
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll} P(k+1): & 5^{k+1}~-~5 & {} & {} & {} \\ {} & 5^k  \times 5~-~5 & {} & \color {silver}{\text{is divisible by 4}}~~\color {green}{\text{---- (a)}} & {} \\ {}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\ P(k+1): & [(4d~+~5) ×5]~-~5 & {} & {} & {} \\ {}& {} & {}& \color {green}{\text{[Using the result in (i)]}} & {} \\ {} & [20d~+~25]~-~5 & {} & {} & {} \\ {} & 20d~+~20 & {} & {} & {} \\ {} & 4(5d~+~5) & {} & \color {silver}{\text{is indeed divisible by 4}} & {}  & {} \\ \end{array}$
• We proved (a) by rearranging it. The rearrangement was done using P(k)
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for all natural numbers.

Solved example 4.5
For every positive integer n, prove that (2 × 7ⁿ) + (3 × 5ⁿ) - 5 is divisible by 24.
Solution:
1. For any positive integer n, let P(n) denote the given statement.
• Then we can write:
$P(n):(2 \times 7^n) + (3 \times 5^n)-5 \; \text{is divisible by 24}$
2. Basic step: (n=1)
$\begin{array}{ll} P(1): & (2 \times 7^1) + (3 \times 5^1)-5 & {} & \color {silver}{\text{is divisible by 24}} & {} \\ {} & 14 + 15 - 5 & {} & {} & {} \\ {} & 24 & {} & \color {silver}{\text{is divisible by 24}} & {} \\ \end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
$\begin{alignat*}{3} P(k)&: (2 \times 7^k) + (3 \times 5^k)-5 &&\text{is divisible by 24} \\ \Rightarrow P(k)&: (2 \times 7^k) + (3 \times 5^k)-5 = 24d &&\;\text{[d is a natural number]} \end{alignat*}$
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll} P(k+1): & (2 \times 7^{k+1}) + (3 \times 5^{k+1})-5 & {} & {} & {} \\ {} & (2 \times 7^k \times 7) + (3 \times 5^k \times 5)-5 & {} & \color {silver}{\text{is divisible by 24}}~~\color {green}{\text{---- (a)}} & {} \\ {}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\ P(k+1): & [(24d~-3\times 5^k~+~5) \times 7]  & {} & {} & {} \\ {}& {}+ (3 \times 5^k \times 5)-5 & {}& \color {green}{\text{[Using the result in (i)]}} & {} \\ {} & [(24 × d × 7~-3 × 5^k × 7~+~5 × 7)] & {} & {} & {} \\ {} & {}+ (3 \times 5^k \times 5)-5 & {} & {} & {} \\ {} & {} & {} & {} & {} \\ {} & 24 × d × 7~-21 × 5^k & {} & {} & {} \\ {} & {}+~35 + 15 \times 5^k ~-~5 & {} & {} & {} \\ {} & {} & {} & {} & {} \\ {} & 24 × d × 7~-6 × 5^k~+~30 & {} & {} & {} \\ {} & 24 × d × 7~-6(5^k~-~5) & {} & {} & {} \\ {} & 24 × d × 7~-6(4m) & {} &\color {green}{\text{[From previous example,   }(5^k~-~5)\text{ is a multiple of 4]}} & {} \\ {}& {} & {}& \color {green}{\text{[m is an integer]}} & {} \\ {}& {} & {}& {} & {} \\ {} & 24 × d × 7~-24m & {} &  {} & {} \\ {} & 24(7d~-~m) & {} &  \color {silver}{\text{is indeed divisible by 24}} & {} \\ \end{array}$
• We proved (a) by rearranging it. The rearrangement was done using P(k)
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for all natural numbers.

Solved example 4.6
For all natural numbers n, prove that:

$$1^2+2^2+3^2+\;.\;.\;.\;+n^2>\frac{n^3}{3}$$
Solution:
1. For all natural numbers n, let P(n) denote the given statement.
• Then we can write:
$P(n):\,1^2+2^2+3^2+\;.\;.\;.\;+n^2>\frac{n^3}{3}$
2. Basic step: (n=1)
$\begin{array}{ll} P(1): & 1^2 & {}>{} & \frac{1^3}{3} & {} \\ {} & 1 & {}>{} & \frac{1}{3} & {} \\ \end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
$P(k): 1^2+2^2+3^2+\;.\;.\;.\;+k^2>\frac{k^3}{3}$
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll} P(k+1): & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+\{(k+1)^2\} & {}>{} & \frac{(k+1)^3}{3} & {} \\ {} & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+\{(k+1)^2\} & {}>{} & \frac{k^3+3k^2+3k+1}{3}~\color {green}{\text{---- (a)}} & {} \\ {}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\ {}&{}& {}&{} & {} \\ P(k): & 1^2+2^2+3^2+\;.\;.\;.\;+k^2 & {}>{} & \frac{k^3}{3}~\color {green}{\text{---- (b)}} & {} \\ {} & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+(k+1)^2 & {}>{} & \frac{k^3}{3}+(k+1)^2~\color {green}{\text{---- (c)}} & {} \\ {}&{}& {}& \color {green}{\text{[Adding}~ (k+1)^2~\text{on both sides]}} & {} \\ {} & {} & {}>{} & \frac{k^3+3(k+1)^2}{3} & {} \\ {} & {} & {}>{} & \frac{k^3+3(k^2+2k+1)}{3} & {} \\ \Rightarrow & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+(k+1)^2 & {}>{} & \frac{k^3+3k^2+6k+3}{3}~\color {green}{\text{---- (d)}} & {} \\ {}&{}& {}&{} & {} \\ {} & \frac{k^3+3k^2+6k+3}{3} & {}>{} & \frac{k^3+3k^2+3k+1}{3}~\color {green}{\text{---- (e)}} & {} \\ {}&{} & {}& \color {green}{\text{[Comparing RHS of (d) and (a)]}} & {} \\ {}&{} & {}& \color {green}{\text{[The denominators are same. So compare numerators]}} & {} \\ {}&{} & {}& \color {green}{\text{['k' is an integer. So (6k+3) > (3k+1)]}} & {} \\ {}&{} & {}& \color {green}{\text{[So (e) is true]}} & {} \\ {}&{}& {}&{} & {} \\ \Rightarrow & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+(k+1)^2 & {}>{} & \frac{k^3+3k^2+6k+3}{3}~~>~~\frac{k^3+3k^2+3k+1}{3}~\color {green}{\text{---- (f)}} & {} \\ {}&{} & {}& \color {green}{\text{[Using (d) and (e)]}} & {} \\ \Rightarrow & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+(k+1)^2 & {}>{} & \frac{k^3+3k^2+3k+1}{3}~\color {green}{\text{---- (f)}} & {} \\ {}&{} & {}& \color {green}{\text{[Picking first and last items from (f)]}} & {} \\ {} &{} & {}& \color {green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\ \end{array}$
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for all natural numbers.

Solved example 4.7
Prove that for every natural number, (ab)ⁿ = aⁿbⁿ
Solution:
1. For all natural numbers n, let P(n) denote the given statement.
• Then we can write:
P(n): (ab)ⁿ = aⁿbⁿ
2. Basic step: (n=1)
$\begin{alignat*}{3} P(1)&: (ab)^1 = a^1 \times b^1 \\ \Rightarrow P(1)&: ab = a \times b = ab \end{alignat*}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
$\begin{alignat*}{3} P(k)&: (ab)^k = a^k \times b^k \\ \Rightarrow P(k)&: (ab)^k = a^k b^k \\ \end{alignat*}$
• Assume that, the above result is true.
(ii) n = k+1
$\begin{alignat*}{3} P(k+1)&: (ab)^{k+1} &&= a^{k+1} \times b^{k+1} \; \text{[We want to prove this to be true]} \\ \Rightarrow P(k+1)&: (ab)^{k+1} &&= a^k \times a \times b^k \times b \\ {}&{} &&= \{a^k \times b^k \} \times \{a \times  b \} \\ {}&{} &&= \{(ab)^k \} \times \{a \times  b \} \; \text{[Using the result in (i)]} \\ {}&{} &&= \{(ab)^k \} \times \{(ab) \} \\ \Rightarrow P(k+1)&: (ab)^{k+1} &&=  (ab)^{k+1} \; \text{[This is true]} \end{alignat*}$
• So P(k+1) is true.
4. Thus P(k+1) is true whenever P(k) is true. Hence by the principle of mathematical induction, P(n) is true for any positive integer n.

---

• The link below gives the folder containing additional solved examples on this chapter.

Additional Solved Examples

---

In the next chapter, we will see complex numbers.

Previous

Contents

Next

Copyright©2022 Higher secondary mathematics.blogspot.com