Differentiation (Part-38) | S N De

Mathematical Induction (Part 2B) | Long Answer Type Questions | Unit-3 (S.N. Dey)

In the previous article, we discussed the first set of Long Answer Type Questions [1(i) - 1(xii)]. In this article, we will discuss the remaining problems from Exercise 3 and their step-by-step solutions. Let's begin.

Exercise 3: Long Answer Type Questions (Continued)

1(xiii) Prove that $\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right) \cdots \left(1-\frac{1}{(n+1)^2}\right)=\frac{n+2}{2n+2}$

Sol. Let $P(n)$ be the statement: $\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right) \cdots \left(1-\frac{1}{(n+1)^2}\right)=\frac{n+2}{2n+2}$

Now, $P(1): 1-\frac{1}{2^2} = 1 - \frac{1}{4} = \frac{3}{4}$.
RHS: $\frac{1+2}{2(1)+2} = \frac{3}{4}$.
Hence, $P(1)$ is true.

Let us suppose $P(m)$ is true.
So, $P(m): \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right) \cdots \left(1-\frac{1}{(m+1)^2}\right)=\frac{m+2}{2m+2}$

Now, for $P(m+1)$:
$\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right) \cdots \left(1-\frac{1}{(m+1)^2}\right)\left(1-\frac{1}{(m+2)^2}\right)$
$= \frac{m+2}{2m+2} \left(1-\frac{1}{(m+2)^2}\right) \quad [\text{By } P(m)]$
$= \frac{m+2}{2(m+1)} \times \frac{(m+2)^2-1}{(m+2)^2}$
$= \frac{m+2}{2(m+1)} \times \frac{(m+1)(m+3)}{(m+2)^2}$
$= \frac{m+3}{2(m+2)}$
$= \frac{(m+1)+2}{2(m+1)+2}$

Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.

1(xiv) Prove that $2+222+22222+\cdots+ \underbrace{22\dots2}_{(2n-1)\text{ digits}} = \frac{20}{891}\left(10^{2n}-1\right)-\frac{2n}{9}$

Sol. Let $P(n)$ be the statement: $2+222+22222+\cdots+ \underbrace{22\dots2}_{(2n-1)\text{ digits}} = \frac{20}{891}\left(10^{2n}-1\right)-\frac{2n}{9}$

Now, $P(1):$ LHS $= 2$.
RHS $= \frac{20}{891}(10^2-1) - \frac{2}{9} = \frac{20}{891}(99) - \frac{2}{9} = \frac{20}{9} - \frac{2}{9} = \frac{18}{9} = 2$.
Hence, $P(1)$ is true.

Let us suppose $P(m)$ is true.
So, $P(m): 2+222+\cdots+ \underbrace{22\dots2}_{(2m-1)\text{ digits}} = \frac{20}{891}\left(10^{2m}-1\right)-\frac{2m}{9}$

Now, for $P(m+1)$:
LHS $= \left[ \frac{20}{891}\left(10^{2m}-1\right)-\frac{2m}{9} \right] + \underbrace{22\dots2}_{(2m+1)\text{ digits}}$
Note that $\underbrace{22\dots2}_{(2m+1)\text{ digits}} = \frac{2}{9}(10^{2m+1}-1)$.
$= \frac{20}{891}\left(10^{2m}-1\right) - \frac{2m}{9} + \frac{2}{9}(10^{2m+1}-1)$
$= \frac{20}{891} \cdot 10^{2m} - \frac{20}{891} - \frac{2m}{9} + \frac{20}{9} \cdot 10^{2m} - \frac{2}{9}$
$= 10^{2m} \left( \frac{20}{891} + \frac{20 \times 99}{891} \right) - \left( \frac{20}{891} + \frac{2m}{9} + \frac{2}{9} \right)$
$= \frac{20}{891} \cdot 10^{2m}(1 + 99) - \frac{20 + 22m + 22}{891}$
$= \frac{20}{891} \cdot 10^{2m+2} - \frac{22m + 42}{891}$
$= \frac{20}{891} \left( 10^{2(m+1)} - 1 \right) - \frac{2(m+1)}{9}$

Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.

1(xv) Prove that $^{n}C_0+^{n}C_1+^{n}C_2+\cdots +^{n}C_n=2^n\,\,(n \in \mathbb{N})$

Sol. Let $P(n)$ be the statement: $^{n}C_0+^{n}C_1+^{n}C_2+\cdots +^{n}C_n=2^n$

Now, $P(1): ^{1}C_0+^{1}C_1 = 1 + 1 = 2 = 2^1$. Hence, $P(1)$ is true.

Let us suppose $P(m)$ is true.
So, $P(m): ^{m}C_0+^{m}C_1+\cdots +^{m}C_m=2^m$

Now, for $P(m+1)$:
$^{m+1}C_0+^{m+1}C_1+\cdots +^{m+1}C_{m+1}$
Using the identity $^{m+1}C_r = ^{m}C_r + ^{m}C_{r-1}$:
$= ^{m}C_0 + \sum_{r=1}^{m} \left( ^{m}C_r + ^{m}C_{r-1} \right) + ^{m+1}C_{m+1}$
$= \left( ^{m}C_0 + ^{m}C_1 + \cdots + ^{m}C_m \right) + \left( ^{m}C_0 + ^{m}C_1 + \cdots + ^{m}C_m \right)$
$= 2^m + 2^m \quad [\text{By } P(m)]$
$= 2^{m+1}$

Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.

2. If $x$ and $y$ are two real numbers, prove by mathematical induction that $(x^n-y^n)$ is divisible by $(x-y)$ for all $n \in \mathbb{N}$.

Sol. Let $P(n)$ be the statement: $(x^n-y^n)$ is divisible by $(x-y)$ for all $n \in \mathbb{N}$.

Now, $P(1): x^1-y^1 = x-y$, which is clearly divisible by $(x-y)$. Hence, $P(1)$ is true.

Let us suppose $P(m)$ is true.
So, $x^m-y^m = k(x-y)$ for some integer $k$.
$\Rightarrow x^m = k(x-y) + y^m \quad \cdots(1)$

Now, for $P(m+1)$:
$x^{m+1}-y^{m+1} = x^m \cdot x - y^m \cdot y$
$= [k(x-y) + y^m]x - y^m \cdot y \quad [\text{By (1)}]$
$= kx(x-y) + xy^m - y^{m+1}$
$= kx(x-y) + y^m(x-y)$
$= (x-y)(kx + y^m)$

Since $kx + y^m$ is a real number, $(x^{m+1}-y^{m+1})$ is divisible by $(x-y)$.
Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.

3. By induction method, prove that $(a^n + b^n)$ is divisible by $(a+b)$ when $n$ is an odd positive integer.

Sol. Let $n = 2k-1$ where $k \in \mathbb{N}$. Let $P(k)$ be the statement: $(a^{2k-1} + b^{2k-1})$ is divisible by $(a+b)$.

Now, $P(1): a^{2(1)-1} + b^{2(1)-1} = a^1 + b^1 = a+b$, which is divisible by $(a+b)$. Hence, $P(1)$ is true.

Let us suppose $P(m)$ is true.
So, $a^{2m-1} + b^{2m-1} = r(a+b)$ for some integer $r$.
$\Rightarrow a^{2m-1} = r(a+b) - b^{2m-1} \quad \cdots(1)$

Now, for $P(m+1)$:
$a^{2(m+1)-1} + b^{2(m+1)-1} = a^{2m+1} + b^{2m+1}$
$= a^2 \cdot a^{2m-1} + b^2 \cdot b^{2m-1}$
$= a^2 [r(a+b) - b^{2m-1}] + b^{2m+1} \quad [\text{By (1)}]$
$= r a^2 (a+b) - a^2 b^{2m-1} + b^{2m+1}$
$= r a^2 (a+b) - b^{2m-1}(a^2 - b^2)$
$= r a^2 (a+b) - b^{2m-1}(a-b)(a+b)$
$= (a+b) [r a^2 - b^{2m-1}(a-b)]$

Thus, it is divisible by $(a+b)$.
Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(k)$ is true for all $k \in \mathbb{N}$, meaning the statement holds for all odd positive integers $n$.

4. If $n \in \mathbb{N}$ and $(2 \cdot 1+1)+(2 \cdot 2+1)+(2 \cdot 3+1)+\dots+ (2n + 1) = n^2 + 2n+5$ is true for $n= m$, then prove that it is also true for $n=m+1$. Can we conclude that it is true for all $n \in \mathbb{N}$?

Sol. Suppose $P(m)$ is true.
So, $P(m): (2 \cdot 1+1)+(2 \cdot 2+1)+\dots+ (2m + 1) = m^2 + 2m+5$

Now, for $P(m+1)$:
LHS $= (2 \cdot 1+1)+(2 \cdot 2+1)+\dots+ (2m + 1) + (2(m+1) + 1)$
$= (m^2 + 2m + 5) + (2m + 3) \quad [\text{By } P(m)]$
$= m^2 + 4m + 8$
RHS for $n=m+1$: $(m+1)^2 + 2(m+1) + 5 = m^2 + 2m + 1 + 2m + 2 + 5 = m^2 + 4m + 8$.
Hence, the statement is true for $n=m+1$ if it is true for $n=m$.

However, let's check the base case $P(1)$:
LHS for $n=1$: $2(1)+1 = 3$.
RHS for $n=1$: $1^2 + 2(1) + 5 = 8$.
Since $3 \neq 8$, $P(1)$ is not true.

Therefore, we cannot conclude that the statement is true for all $n \in \mathbb{N}$, because the foundation (base case) of mathematical induction fails.

5. Prove by induction that $n(n^2-1)$ is divisible by $24$ when $n$ is an odd positive integer.

Sol. Since $n$ is an odd positive integer, let $n = 2k-1$ for $k \in \mathbb{N}$.
Then, $n(n^2-1) = (2k-1)[(2k-1)^2-1] = (2k-1)(2k-1+1)(2k-1-1) = (2k-1)(2k)(2k-2) = 4k(k-1)(2k-1)$.

Let $P(k)$ be the statement: $4k(k-1)(2k-1)$ is always divisible by $24$.

Now, $P(1): 4(1)(0)(1) = 0$, which is divisible by $24$. So, $P(1)$ is true.

Let $P(m)$ be true.
So, $4m(m-1)(2m-1) = 24r$ for some integer $r$.
$\Rightarrow 2m^3 - 3m^2 + m = 6r \quad \cdots(1)$

Now, for $P(m+1)$:
$4(m+1)(m)(2(m+1)-1) = 4(m+1)(m)(2m+1) = 4(2m^3 + 3m^2 + m)$
$= 4 [ (2m^3 - 3m^2 + m) + 6m^2 ]$
$= 4 [ 6r + 6m^2 ] \quad [\text{By (1)}]$
$= 24(r + m^2)$

Thus, it is divisible by $24$.
Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(k)$ is true for all $k \ “in \mathbb{N}$, meaning the original statement holds for all odd positive integers $n$.

6. Find the positive integer $n$ for which the inequality $2^n > n^2$ holds.

Sol. Let's test small values of $n$:
$P(1): 2^1 > 1^2 \Rightarrow 2 > 1$ (True)
$P(2): 2^2 > 2^2 \Rightarrow 4 > 4$ (False)
$P(3): 2^3 > 3^2 \Rightarrow 8 > 9$ (False)
$P(4): 2^4 > 4^2 \Rightarrow 16 > 16$ (False)
$P(5): 2^5 > 5^2 \Rightarrow 32 > 25$ (True)
$P(6): 2^6 > 6^2 \Rightarrow 64 > 36$ (True)

Let us assume $P(n)$ is true for $n \geq 5$. We have shown $P(5)$ is true.

Let $P(m)$ be true for some $m \geq 5$. Then, $2^m > m^2$.
We also know that for $m \geq 5$, $2^m > 2m + 1$ (as proven in Part 2A).

Now, for $P(m+1)$:
$2^{m+1} = 2^m + 2^m > m^2 + (2m + 1) = (m+1)^2$.
Thus, $2^{m+1} > (m+1)^2$.

Since $P(5)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, the inequality $2^n > n^2$ holds for $n = 1$ and for all $n \geq 5$.

7. Prove by mathematical induction that for all $n \in \mathbb{N}$, when $3^{2n}$ is divided by $8$, the remainder is always $1$.

Sol. Let $P(n)$ be the statement: $3^{2n} = 8k + 1$ for some integer $k$.

Now, $P(1): 3^{2(1)} = 9 = 8(1) + 1$. The remainder is $1$. Hence, $P(1)$ is true.

Let $P(m)$ be true.
So, $3^{2m} = 8k + 1$ for some integer $k$.

Now, for $P(m+1)$:
$3^{2(m+1)} = 3^{2m+2} = 9 \cdot 3^{2m}$
$= 9(8k + 1) \quad [\text{By } P(m)]$
$= 72k + 9$
$= 8(9k + 1) + 1$

Thus, when divided by $8$, the remainder is $1$.
Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.

8. Prove by induction that $5^{n+1} + 4 \cdot 6^n$ when divided by $20$ leaves the same remainder $9$ for all $n \in \mathbb{N}$.

Sol. Let $P(n)$ be the statement: $5^{n+1} + 4 \cdot 6^n = 20k + 9$ for some integer $k$.

Now, $P(1): 5^{1+1} + 4 \cdot 6^1 = 25 + 24 = 49 = 20(2) + 9$. The remainder is $9$. Hence, $P(1)$ is true.

Let $P(m)$ be true.
So, $5^{m+1} + 4 \cdot 6^m = 20k + 9$.
$\Rightarrow 5^{m+1} = 20k + 9 - 4 \cdot 6^m \quad \cdots(1)$

Now, for $P(m+1)$:
$5^{(m+1)+1} + 4 \cdot 6^{m+1} = 5 \cdot 5^{m+1} + 24 \cdot 6^m$
$= 5(20k + 9 - 4 \cdot 6^m) + 24 \cdot 6^m \quad [\text{By (1)}]$
$= 100k + 45 - 20 \cdot 6^m + 24 \cdot 6^m$
$= 100k + 45 + 4 \cdot 6^m$
$= 100k + 45 + 4(1 + 5)^m$

Using the Binomial Theorem on $(1+5)^m$:
$(1+5)^m = 1 + \binom{m}{1}5 + \binom{m}{2}5^2 + \dots + \binom{m}{m}5^m$
So, $4(1+5)^m = 4 + 20\left[ \binom{m}{1} + \binom{m}{2}5 + \dots + \binom{m}{m}5^{m-1} \right]$

Substituting back:
$= 100k + 45 + 4 + 20 \cdot M \quad (\text{where } M \text{ is an integer})$
$= 100k + 49 + 20M$
$= 20(5k + M + 2) + 9$

Thus, when divided by $20$, the remainder is $9$.
Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.

9. Prove by induction that $8 \cdot 7^n + 4^{n+2}$ is divisible by $24$ but not by $48$ for all $n \in \mathbb{N}$.

Sol. Part 1: Divisibility by 24
Let $P(n)$ be the statement: $8 \cdot 7^n + 4^{n+2}$ is divisible by $24$.

Now, $P(1): 8 \cdot 7^1 + 4^{1+2} = 56 + 64 = 120$, which is divisible by $24$ ($120 = 24 \times 5$). Hence, $P(1)$ is true.

Let $P(m)$ be true.
So, $8 \cdot 7^m + 4^{m+2} = 24k$ for some integer $k$.
$\Rightarrow 4^{m+2} = 24k - 8 \cdot 7^m \quad \cdots(1)$

Now, for $P(m+1)$:
$8 \cdot 7^{m+1} + 4^{(m+1)+2} = 8 \cdot 7 \cdot 7^m + 4 \cdot 4^{m+2}$
$= 56 \cdot 7^m + 4(24k - 8 \cdot 7^m) \quad [\text{By (1)}]$
$= 56 \cdot 7^m + 96k - 32 \cdot 7^m$
$= 24 \cdot 7^m + 96k$
$= 24(7^m + 4k)$

Thus, it is divisible by $24$. Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.

Part 2: Not divisible by 48
Let $Q(n)$ be the statement: $8 \cdot 7^n + 4^{n+2}$ is divisible by $48$.
Check the base case $Q(1)$: $8 \cdot 7^1 + 4^3 = 120$.
$120$ is not divisible by $48$ ($120 / 48 = 2.5$).
Since the base case fails, $Q(n)$ is false for all $n \in \mathbb{N}$.

10. Prove by induction that $2^{2^n} + 1$ has $7$ in the unit's place for all $n \geq 2$.

Sol. Let $P(n)$ be the statement: $2^{2^n} + 1 \equiv 7 \pmod{10}$ for all $n \geq 2$.

Now, $P(2): 2^{2^2} + 1 = 2^4 + 1 = 16 + 1 = 17$. The unit's digit is $7$. Hence, $P(2)$ is true.

Let $P(m)$ be true for some $m \geq 2$.
So, $2^{2^m} + 1 = 10p + 7$ for some integer $p$.
$\Rightarrow 2^{2^m} = 10p + 6 \quad \cdots(1)$

Now, for $P(m+1)$:
$2^{2^{m+1}} + 1 = 2^{2^m \cdot 2} + 1 = (2^{2^m})^2 + 1$
$= (10p + 6)^2 + 1 \quad [\text{By (1)}]$
$= 100p^2 + 120p + 36 + 1$
$= 100p^2 + 120p + 37$
$= 10(10p^2 + 12p + 3) + 7$

Thus, the unit's digit is $7$.
Since $P(2)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \geq 2$.

11. Using mathematical induction, prove that for every integer $n$, $|\sin{nx}| \leq n|\sin x|$.

Sol. Let $P(n)$ be the statement: $|\sin{nx}| \leq n|\sin x|$ for all $n \in \mathbb{N}$.

Now, $P(1): |\sin(1 \cdot x)| \leq 1 \cdot |\sin x| \Rightarrow |\sin x| \leq |\sin x|$, which is trivially true. Hence, $P(1)$ is true.

Let $P(m)$ be true.
So, $|\sin{mx}| \leq m|\sin x| \quad \cdots(1)$

Now, for $P(m+1)$:
$|\sin((m+1)x)| = |\sin(mx + x)|$
Using the identity $\sin(A+B) = \sin A \cos B + \cos A \sin B$:
$= |\sin(mx)\cos x + \cos(mx)\sin x|$
Using the triangle inequality $|a+b| \leq |a| + |b|$:
$\leq |\sin(mx)\cos x| + |\cos(mx)\sin x|$
$\leq |\sin(mx)| \cdot |\cos x| + |\cos(mx)| \cdot |\sin x|$

Since $|\cos \theta| \leq 1$ for any real $\theta$:
$\leq |\sin(mx)| \cdot 1 + 1 \cdot |\sin x|$
$\leq m|\sin x| + |\sin x| \quad [\text{By (1)}]$
$= (m+1)|\sin x|$

Thus, $|\sin((m+1)x)| \leq (m+1)|\sin x|$.
Since $P(1)$ is true and $P(m)$ is true $\Rightarrow P(m+1)$ is true.
So, $P(n)$ is true for all $n \in \mathbb{N}$.