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

Chapter 4.1 - Problems Involving Inequalities

In the previous section, we saw the basics of mathematical induction. We saw some examples also. In this section we will see problems involving inequality.

Let us see an example. It can be written in 4 steps:
1. Consider any positive integer n. A mathematician tells us that, this n will be always less than twice it's value.
That is: n < 2n
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 1
• Put n = 1 in the RHS. We get: RHS = 2 × 1 = 2
• LHS < RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = k
• Put n = k in the RHS. We get: 2 × k = 2k
• We assume that, this LHS is less than RHS. That is., k < 2k
(ii) Put n = (k+1) in the LHS. We get: LHS = k+1
• Put n = (k+1) in the RHS. We get: RHS = 2(k+1) = 2k+2
(iii) We have to prove that LHS in (ii) is less than RHS in (ii)
• That is., we have to prove that: k+1 < 2k+2
   ♦ For proving this, we can use the statement in (i)
   ♦ Remember that, we assume the statement in (i) to be true.
(iv) Consider the statement in (i): k < 2k
• Adding '1' on both sides, we get: k+1 < 2k+1
• So k+1 will be obviously less than 2k+2
• Thus the statement in (iii) is proved.
• So we proved that:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.

---

Let us write the above steps in the condensed form:

Problem:
Prove that for any positive integer n, n  < 2n

Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: P(n): n < 2n
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): & 1 & {}<{} & (2 × 1) & {} \\
{\Rightarrow~} P(1): & 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): k < 2k
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll}
\phantom{\Rightarrow~}P(k+1): & k+1 & {}<{} & 2(k+1) & {} \\
{\Rightarrow~} P(k+1): & k+1 & {}<{} & 2k+2~\color {green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
\phantom{\Rightarrow~}P(k): & k & {}<{} & 2k~\color {green}{\text{---- (b)}} & {} \\
{} & k+1 & {}<{} & 2k+1~\color {green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color {green}{\text{[Adding '1' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 2k+1 & {}<{} & 2k+2~\color {green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color {green}{\text{[Since 'k' is a +ve integer]}} & {} \\
{}&{}& {}&{} & {} \\
{} & k+1 & {}<{} & 2k+1 ~~ <~~2k+2 & {} \\
{}&{} & {}& \color {green}{\text{[Using (c) and (d)]}} & {} \\
{} & k+1 & {}<{} & 2k+2 & {} \\
{}&{} & {}& \color {green}{\text{[Picking first and third items]}} & {} \\
{}&{} & {}& \color {green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\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.
5. We can write the conclusion in another way also:
• We want to prove that k+1 < 2k+2
• In (ii), we saw that, k+1 < 2k+1
• Since k is positive integer, 2k+1 will be less than 2k+2
• So we can write: k+1 < 2k+1 < 2k+2
• Picking the first and last expressions, we get: k+1 < 2k+2

---

Let us see another example. It can be written in 4 steps:
1. Consider any positive integer n. A mathematician tells us that, this n will be always less than 2 raised to n.
That is: 2ⁿ > n
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 2¹ × 1 = 2
• Put n = 1 in the RHS. We get: RHS = 1
• LHS > RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = 2^k
• Put n = k in the RHS. We get: RHS = k
• We assume that, this LHS is greater than RHS. That is., 2^k > k
(ii) Put n = (k+1) in the LHS. We get: LHS = 2^k+1
• Put n = (k+1) in the RHS. We get: RHS = k+1
(iii) We have to prove that LHS in (ii) is greater than RHS in (ii)
• That is., we have to prove that: 2^k+1 > k+1
   ♦ For proving this, we can use the statement in (i)
   ♦ Remember that, we assume the statement in (i) to be true.
(iv) Statement in (i) is: 2^k > k
• Adding 1 on both sides, we get: 2^k +1 > k+1 
(v) Let us replace the '1' on the left side by 2^k. We get:
2^k + 2^k > k+1
• This is true because, k is a +ve integer. 2^k will be greater than 1.
(vi) The left side can be simplified. We get: 2 × 2^k > k+1
• This is same as: 2^k+1 > k+1
• So the statement in (iii) is true.
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.

---

Let us write the above steps in the condensed form:

Problem:
Prove that for any positive integer n, 2ⁿ > n

Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: P(n): 2ⁿ > n
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): & 2^1 & {}>{} & 1 & {} \\
{\Rightarrow~} P(1): & 2 & {}>{} & 1 & {} \\
\end{array}$
• So P(n) is true for n=1
3. Inductive step: (n=k) and (n= k+1)
(i) n= k
P(k): 2^k > k
• Assume that, the above statement is true.
(ii) n = k+1
$\begin{array}{ll}
P(k+1): & 2^{k+1} & {}>{} & k+1~\color {green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
P(k): & 2^k & {}>{} & k~\color {green}{\text{---- (b)}} & {} \\
{} & 2^k+1 & {}>{} & k+1~\color {green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color {green}{\text{[Adding '1' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 2^k & {}>{} & 1~\color {green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color {green}{\text{[Since 'k' is a +ve integer]}} & {} \\
{} & 2^k+2^k & {}>{} & k+1~\color {green}{\text{---- (e)}} & {} \\
{}&{} & {}& \color {green}{\text{[Using (c) and (d)]}} & {} \\
\Rightarrow & 2 × 2^k & {}>{} & k+1 & {} \\
\Rightarrow & 2^{k+1} & {}>{} & k+1 & {} \\
{} &{} & {}& \color {green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\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.

---

Let us see another problem involving inequality. It can be written in 4 steps:
1. Consider any positive integer n. A mathematician tells us that, '4' raised to this n will be always greater than (n+1).
That is: 4ⁿ > n+1
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 4¹ = 4
• Put n = 1 in the RHS. We get: RHS = 1+1 = 2
• LHS > RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = 4^k
• Put n = k in the RHS. We get: RHS = k+1
• We assume that, this LHS is greater than RHS. That is., 4^k > k+1
(ii) Put n = (k+1) in the LHS. We get: LHS = 4^(k+1)
• Put n = (k+1) in the RHS. We get: RHS = (k+1)+1
(iii) We have to prove that LHS in (ii) is greater than RHS in (ii)
• That is., we have to prove that: 4^(k+1) > (k+1)+1
   ♦ For proving this, we can use the statement in (i)
   ♦ Remember that, we assume the statement in (i) to be true.
(iv) In (i), it is said that, 4^k is greater than (k+1)
• So (4^k +1) will be greater than [(k+1)+1]
• So (4^k + 4^k) will be greater than [(k+1)+1] (since k is a positive number, 4^k will be greater than 1)
⇒ (2 × 4^k) will be greater than [(k+1)+1]
• So (4^k × 4^k) will be greater than [(k+1)+1] (since k is a positive number, 4^k will be greater than 2)
⇒ 4^(k+1) will be greater than [(k+1)+1]
Thus we proved that: 4^(k+1) > (k+1)+1
• That is:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.

---

Let us write the above steps in the condensed form:

Problem:
Prove that for any positive integer n, 4ⁿ > n+1

Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: P(n): 4ⁿ > n+1
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): & 4^1 & {}>{} & 1+1 & {} \\
{\Rightarrow~} P(1): & 4 & {}>{} & 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): 4^k > k+1
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll}
P(k+1): & 4^{k+1} & {}>{} & k+1+1~\color {green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
P(k): & 4^k & {}>{} & k+1~\color {green}{\text{---- (b)}} & {} \\
{} & 4^k+1 & {}>{} & k+1+1~\color {green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color {green}{\text{[Adding '1' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 4^k & {}>{} & 1~\color {green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color {green}{\text{[Since 'k' is a +ve integer]}} & {} \\
{} & 4^k+4^k & {}>{} & k+1+1~\color {green}{\text{---- (e)}} & {} \\
{}&{} & {}& \color {green}{\text{[Using (c) and (d)]}} & {} \\
\Rightarrow & 2 × 4^k & {}>{} & k+1+1~\color {green}{\text{---- (f)}} & {} \\
{}&{}& {}&{} & {} \\
{} & 4 & {}>{} & 2~\color {green}{\text{---- (g)}} & {} \\
{} & 4 × 4^k & {}>{} & k+1+1 & {} \\
{}&{} & {}& \color {green}{\text{[Using (f) and (g)]}} & {} \\
\Rightarrow & 4^{k+1} & {}>{} & k+1+1 & {} \\
{} &{} & {}& \color {green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\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.

---

Let us see another problem involving inequality. We will directly write the solution in the condensed form.

Problem:
Prove that for positive integer n, 2n+1 < 2ⁿ, n ≥ 3

Solution:
1. For positive integer n ≥ 3, let P(n) denote the given statement.
Then we can write: P(n): 2n+1 < 2ⁿ, n ≥ 3
2. Basic step: (n=3)
$\begin{array}{ll}
P(3): & [(2 × 3)+1] & {}<{} & 2^3 & {} \\
{} & [6+1] & {}<{} & 8 & {} \\
{} & 7 & {}<{} & 8 & {} \\
\end{array}$
• So P(n) is true for n=3
3. Inductive step: (n=k) and (n= k+1)
(i) n= k [positive integer k ≥ 3]
P(k): 2k+1 < 2^k
• Assume that, the above result is true.
(ii) n = k+1
$\begin{array}{ll}
P(k+1): & 2(k+1)+1 & {}<{} & 2^{k+1} & {} \\
{} & 2k+2+1 & {}<{} & 2^{k+1}~\color {green}{\text{---- (a)}} & {} \\
{}& {} & {}& \color {green}{\text{[We want to prove (a)]}} & {} \\
{}&{}& {}&{} & {} \\
P(k): & 2k+1 & {}<{} & 2^k~\color {green}{\text{---- (b)}} & {} \\
{} & 2k+2+1 & {}<{} & 2^k+2~\color {green}{\text{---- (c)}} & {} \\
{}&{}& {}& \color {green}{\text{[Adding '2' on both sides]}} & {} \\
{}&{}& {}&{} & {} \\
{} & 2^k & {}>{} & 2~\color {green}{\text{---- (d)}} & {} \\
{}&{} & {}& \color {green}{\text{[Since k ≥ 3]}} & {} \\
{} & 2k+2+1 & {}<{} & 2^k+2^k & {} \\
{}&{} & {}& \color {green}{\text{[Using (c) and (d)]}} & {} \\
\Rightarrow & 2k+2+1 & {}<{} & 2 × 2^k & {} \\
\Rightarrow & 2k+2+1 & {}<{} & 2^{k+1} & {} \\
{} &{} & {}& \color {green}{\text{[Starting from (b), statement in (a) is proved]}} & {} \\
\end{array}$
• That is., 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

---

In the next section, we will see more solved examples.

Previous

Contents

Next

Copyright©2021 Higher secondary mathematics.blogspot.com

Chapter 4 - Principle of Mathematical Induction

In the previous section, we completed a discussion on trigonometry. In this chapter we will see Principle of mathematical induction.

Some basic details can be written in 9 steps:
1. Consider the three statements below:
(i) All fruits have seeds.
(ii) Apple have seeds.
(iii) So apple is a fruit.
• The first two are general statements. We use those two general statements to arrive at a specific conclusion. The conclusion is the third statement.
2. Let us see another example:
We have three statements:
(i) All numbers ending in 0 and 5 are divisible by 5
(ii) 75 is a number which ends in 5
(iii) So 75 is divisible by 5
• The first two are general statements. We use those two general statements to arrive at a specific conclusion. The conclusion is the third statement.
3. In each of the above two examples, we used two general statements to arrive at a specific statement. That is., we worked from ‘general’ to ‘specific’. This type of reasoning is known as deductive reasoning.
4. The opposite happens in inductive reasoning. That is., we observe specific cases and based on them, we give a general conclusion.
Let us see an example. As before, there are three statements:
(i) Last year rainy season began on 1st of July.
(ii) The year before that also, rainy season began on 1st of July.
(iii) So every year, rainy season begins on 1st of July.
• The first two are specific statements. We use those two specific statements to arrive at a general conclusion. The conclusion is the third statement.
5. Let us see another example:
(i) Walls of the bedroom are painted blue.
(ii) Walls of the dining room are also painted blue.
(iii) So all rooms of the house are painted blue.
• The first two are specific statements. We use those two specific statements to arrive at a general conclusion. The conclusion is the third statement.
6. In each of the above two examples, we used two specific statements to arrive at a general statement. That is., we worked from ‘specific’ to ‘general’. This type of reasoning is known as inductive reasoning.
7. In inductive reasoning, the conclusion can be challenged. That is., the conclusion may or may not be true.  
◼ For example:
• Beginning of rainy season on the 1st of July for two consecutive years, gives no guarantee that, rainy season begins on that day every year.
• Finding blue walls in bedroom and dining room gives no guarantee that, walls of all rooms in the house will be blue.
8. But when we use inductive reasoning in mathematics, we take special precautions so that, the conclusion will be always true.
• The method of inductive reasoning used in mathematics is known as mathematical induction.
9. The basics of mathematical induction can be demonstrated using an example. It can be written in 5 steps:
(i) Fig.4.1(a) below shows some thin tiles placed on their edges. They are placed in a row.

Fig.4.1

 
(ii) If the first tile is pushed, all the tiles will fall. This is shown in fig.b
We want to prove that all tiles have fallen.
(iii) For that we need the following two statements to be true:
   ♦ (a) The first tile is pushed
   ♦ (b) If any tile is pushed, the tile coming just after it will fall.
(iv) Note the significance of statement (a):
It is compulsory that, first tile is pushed. Instead of the first tile, if we push any intermediate tile, only those tiles coming after it will fall. We want the entire row to fall. For that, the pushing of the first tile is necessary.
(v) Note the significance of statement (b). It is self explanatory. If this statement is not true, we cannot guarantee that the entire row will fall.

---

Let us apply the step (9) above to a math problem. It can be written in 4 steps:
1. Consider the sum of n positive integers. A mathematician tells us that, the sum can be calculated using the statement:
$1+2+3+\;.\;.\;.\;+n=\frac{n(n+1)}{2}$
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 1
• Put n = 1 in the RHS. We get: RHS = $\frac{1(1+1)}{2}=\frac{1 × 2}{2}=1$
• LHS = RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 6 steps:
(i) Put n = k in the LHS. We get: LHS = $1+2+3+\;.\;.\;.\;+k$
• Put n = k in the RHS. We get: RHS = $\frac{k(k+1)}{2}$
• We assume that, this LHS and RHS are equal
(ii) Put n = (k+1) in the LHS. We get: LHS = $1+2+3+\;.\;.\;.\;+k+(k+1)$
• Put n = (k+1) in the RHS. We get: RHS = $\frac{(k+1)[(k+1)+1]}{2}$    
(iii) Consider the LHS in (ii). It can be written as: $1+2+3+\;.\;.\;.\;+k+\{(k+1)\}$
• The portion outside the curly brackets, is the LHS in (i)
• We assumed that the LHS in (i) is equal to the RHS in (i)
• So the LHS in (ii) becomes: $\frac{k(k+1)}{2}+\{(k+1)\}$
   ♦ This can be simplified as:
$\frac{k(k+1)}{2}+\{(k+1)\}~=~\frac{k^2+k+2k+2}{2}~=~\frac{k^2+3k+2}{2}$
(iv) Consider the RHS in (ii).
   ♦ This RHS can be simplified as:
$\frac{(k+1)[(k+1)+1]}{2}~=~\frac{(k+1)(k+2)}{2}~=~\frac{k^2+3k+2}{2}$
(v) So from (iii) and (iv) we get:
LHS in (ii) = RHS in (ii)
• That means, the statement is true for n = (k+1)
(vi) But remember that, '(k+1)' passed the test because we assumed that the statement is true for n = k
• So we proved that:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n= (k+1)
• Since both are proved, we can write:
The given statement is true.

---

Let us see another example. It can be written in 4 steps:
1. Consider the sum of n odd numbers. A mathematician tells us that, the sum will be equal to the square of the ‘number of terms added’. In statement form, it can be written as:
$1+3+5+7+\;.\;.\;.\;+(2n-1)=n^2$
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 1
• Put n = 1 in the RHS. We get: RHS = $1^2=1$
• LHS = RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 6 steps:
(i) Put n = k in the LHS. We get: LHS = $1+3+5+7+\;.\;.\;.\;+(2k-1)$
• Put n = k in the RHS. We get: RHS = $k^2$
• We assume that, this LHS and RHS are equal
(ii) Put n = (k+1) in the LHS. We get: LHS = $1+3+5+7+\;.\;.\;.\;+(2k-1)+[2(k+1)-1]$
⇒ LHS = $1+3+5+7+\;.\;.\;.\;+(2k-1)+[2k+2-1]$
⇒ LHS = $1+3+5+7+\;.\;.\;.\;+2k-1+2k+1$
• Put n = (k+1) in the RHS. We get: RHS = $(k+1)^2$    
(iii) Consider the LHS in (ii). It can be written as: $1+3+5+7+\;.\;.\;.\;+2k-1+\{2k+1\}$
• The portion outside the curly brackets, is the LHS in (i)
• We assumed that the LHS in (i) is equal to the RHS in (i)
• So the LHS in (ii) becomes: $k^2+\{2k+1\}$
   ♦ This can be simplified as: $(k+1)^2$
(iv) Consider the RHS in (ii). It is also: $(k+1)^2$
(v) So from (iii) and (iv) we get:
LHS in (ii) = RHS in (ii)
• That means, the statement is true for n = (k+1)
(vi) But remember that, '(k+1)' passed the test because we assumed that the statement is true for n = k
• So we proved that:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n= (k+1)
• Since both are proved, we can write:
The given statement is true.

---

Let us see one more example. It can be written in 4 steps:
1. Consider the sum of the squares of n natural numbers. A mathematician tells us that, the sum can be calculated using the statement:
$1^2+2^2+3^2+4^2+\;.\;.\;.\;+n^2=\frac{n(n+1)(2n+1)}{6}$
• We want to prove this statement.
2. First we prove that, this statement is true when n = 1
• Put n = 1 in the LHS. We get LHS = 1² = 1
• Put n = 1 in the RHS. We get:
RHS = $\frac{1(1+1)(2 × 1+1)}{6}$
⇒ RHS = $\frac{1(2)(3)}{6}$ = 1
• LHS = RHS. So the statement is true when n = 1
◼ This step is called basic step.
3. Next we prove this:
If the statement is true for a positive integer ‘k’, it will be true for the next positive integer (k+1)
• This can be proved in 5 steps:
(i) Put n = k in the LHS. We get: LHS = $1^2+2^2+3^2+4^2+\;.\;.\;.\;+k^2$
• Put n = k in the RHS. We get: RHS = $\frac{k(k+1)(2k+1)}{6}$
• We assume that, this LHS and RHS are equal
(ii) Put n = (k+1) in the LHS. We get: LHS = $1^2+2^2+3^2+4^2+\;.\;.\;.\;+k^2+(k+1)^2$
• Put n = (k+1) in the RHS. We get: RHS = $\frac{(k+1)[(k+1)+1][2(k+1)+1]}{6}$
(iii) Consider the LHS in (ii). It can be written as: $1^2+2^2+3^2+4^2+\;.\;.\;.\;+k^2+\{(k+1)^2\}$
• The portion outside the curly brackets, is the LHS in (i)
• We assumed that the LHS in (i) is equal to the RHS in (i)
• So the LHS in (ii) becomes: $\frac{k(k+1)(2k+1)}{6}+\{(k+1)^2\}$
   ♦ This can be simplified as:
$\frac{k(k+1)(2k+1)}{6}+\{(k+1)^2\}~=~\frac{(k+1)[k(2k+1)]~+~6(k+1)^2}{6}$
${}=~\frac{(k+1)[k(2k+1)~+~6(k+1)]}{6}~=~\frac{(k+1)[2k^2+7k+6]}{6}$
${}=\frac{2k^3+7k^2+6k+2k^2+7k+6}{6}~=~\frac{2k^3+9k^2+13k+6}{6}$
(iv) Consider the RHS in (ii).
   ♦ This RHS can be simplified as:
$\frac{(k+1)[(k+1)+1][2(k+1)+1]}{6}~=~\frac{(k+1)[k+2][2k+3]}{6}$
${}=~\frac{(k+1)[2k^2+3k+4k+6]}{6}=~\frac{2k^3+3k^2+4k^2+6k+2k^2+3k+4k+6}{6}$
${}=~\frac{2k^3+9k^2+13k+6}{6}$
(v) So from (ii) and (iii) we get:
LHS in (ii) = RHS in (ii)
• That means, the statement is true for n = (k+1)
(vi) But remember that, '(k+1)' passed the test because we assumed that the statement is true for n = k
• So we proved that:
If the statement is true for n = k, it will be true for n = (k+1)
◼ This step is called inductive step.
4. So we used basic step in (2) and inductive step in (3)
• In the basic step, we proved that:
The given statement is true when n = 1
• In the inductive step, we proved that:
If the given statement is true for n = k, it will be true for n = (k+1)
• Since both are proved, we can write:
The given statement is true.

---

• In the above problem, what the mathematician said, is a statement. We can write two points here:
(i) The statement is: $1^2+2^2+3^2+4^2+\;.\;.\;.\;+n^2=\frac{n(n+1)(2n+1)}{6}$
   ♦ It is a statement in 'n'
(ii) We can denote the statement as: P(n)

◼  The two points can be combined together as:
$P(n):1^2+2^2+3^2+4^2+\;.\;.\;.\;+n^2=\frac{n(n+1)(2n+1)}{6}$

---

• Using this information, let us see a condensed form for writing the solution of the above problem.

Problem:
Prove that for any positive integer n, $1^2+2^2+3^2+4^2+\;.\;.\;.\;+n^2=\frac{n(n+1)(2n+1)}{6}$

Solution:
1. For any positive integer n, let P(n) denote the given statement.
Then we can write: $P(n):1^2+2^2+3^2+4^2+\;.\;.\;.\;+n^2=\frac{n(n+1)(2n+1)}{6}$
2. Basic step: (n=1)
$\begin{array}{ll}
\phantom{\Rightarrow~}P(1): & 1^2 & {}={} & \frac{1(1+1)(2 × 1+1)}{6} & {} \\
{\Rightarrow~} P(1): & 1^2 & {}={} & \frac{1 × 2 × 3}{6} & {} \\
{} & 1^2 & {}={} & \frac{6}{6} & {} \\
{} & 1 & {}={} & 1 & {} \\
\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(k+1)(2k+1)}{6}$
• Assume that, this is true.
(ii) n = k+1
$\begin{array}{ll}
\phantom{\Rightarrow~}P(k+1): & 1^2+2^2+3^2+\;.\;.\;.\;+k^2+[(k+1)^2] & {}={} & \frac{(k+1)[(k+1)+1][2(k+1)+1]}{6} & {} \\
{\Rightarrow~} P(k+1): & \frac{k(k+1)(2k+1)}{6}+[(k+1)^2] & {}={} & \frac{(k+1)[(k+1)+1][2(k+1)+1]}{6} & {} \\
{}&\color {green}{\text{[Using result in (i)]}} & {}&{} & {} \\
{\Rightarrow~} P(k+1): & \frac{(k+1)[k(2k+1)]~+~6(k+1)^2}{6} & {}={} & \frac{(k+1)[k+2][2k+3]}{6} & {} \\
{} & \frac{(k+1)[k(2k+1)~+~6(k+1)]}{6} & {}={} & \frac{(k+1)[2k^2+3k+4k+6]}{6} & {} \\
{} & \frac{(k+1)[2k^2+7k+6]}{6} & {}={} & \frac{2k^3+3k^2+4k^2+6k+2k^2+3k+4k+6}{6} & {} \\
{} & \frac{2k^3+7k^2+6k+2k^2+7k+6}{6} & {}={} & \frac{2k^3+9k^2+13k+6}{6} & {} \\
{} & \frac{2k^3+9k^2+13k+6}{6} & {}={} & \frac{2k^3+9k^2+13k+6}{6} & {} \\
\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 any positive integer n.

---

In the next section, we will see problems involving inequality.

Previous

Contents

Next

Copyright©2022 Higher secondary mathematics.blogspot.com