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