Mathematical induction is a mathematical tool used to that a given formula, statement is true for all natural numbers n = 1, 2, 3, ...
There are total three steps to check whether given statement is true by using Mathematical induction
1). Show that given statement is true for n=1.
2). If it is true for n=1, then assume that this is true for n=k.
3). Now put n=k+1 in initial statement and make use of above (true for n=k) to show that statement is true for n=k+1
and you are done, let us see some example.
\[1+2+3+ \cdots +n =\displaystyle \frac{n(n+1)}{2} \]
Solution : Let us first check for \(n=1\)
when we take \(n=1\) we get \[ 1 = \displaystyle \frac{1(2)}{2}=1\] so we have LHS =RHS
Now we will assume that result is true for \(n=m\)
i.e \[1+2+3+\cdots+m=\displaystyle \frac{m(m+1)}{2}\] we will prove the result is true for \(n=m+1\)
lets take \(n=m+1\)
we get the right hand side \[\displaystyle \frac{(m+1)(m+2)}{2}\] and the left hand side can be written as
\[1+2+3+\cdots+m+(m+1)\] from (1) we have \[\displaystyle \frac{m(m+1)}{2} +(m+1)\] whihc an be written as \[=\displaystyle \frac{(m+1)(m+2)}{2}\] from (2) and (3) we can conclude that \[1+2+3+ \cdots +n =\displaystyle \displaystyle \frac{n(n+1)}{2} \]
Question 2: Using Mathematical Induction show that for all \(n \geq 1\)
\[ 1+a+a^{2}+\ldots .+a^{n-1}=\displaystyle \displaystyle \frac{a^{n}-1}{a-1} \]
Solution : In question we are given that
\[
1+a+a^{2}+\ldots .+a^{n-1}=\displaystyle \displaystyle \frac{a^{n}-1}{a-1}
\]
First we show that this is true for \(n=1\), so put \(n=1\)
\[ a^{1-1}=\displaystyle \displaystyle \frac{a^{1}-1}{a-1} \] \[1=1\] so left hand side = rigt hand side
let us suppose that this is true, for \(n=k\) i.e
\begin{equation} 1+a+a^{2}+\ldots . .+a^{k-1}=\displaystyle \displaystyle \frac{a^{k}-1}{a-1} \end{equation} Now we will prove this is true, for \(n=k+1\)
i.e \[ 1+a+a^{2}+\ldots .+a^{k+1-1}=\displaystyle \displaystyle \frac{a^{k+1}-1}{a-1} \] The left hand side can be written as \[1+a+a^{2}+\ldots .+a^{k}\] \[=\left(1+a+a^{2}+\ldots \ldots+a^{k-1}\right)+a^{k}\] from (1) we have \[=\displaystyle \displaystyle \frac{a^{k}-1}{a-1}+a^{k}\] taking LCM and re arranging we get \[= \displaystyle \frac{a^{k}-1+a^{k} \cdot a-a^{k}}{a-1}\] \[=\displaystyle \displaystyle \frac{a^{k+1}-1}{a-1}\] which is equal to right hand side of
So this is true by mathematical induction .
\[ a^{1-1}=\displaystyle \displaystyle \frac{a^{1}-1}{a-1} \] \[1=1\] so left hand side = rigt hand side
let us suppose that this is true, for \(n=k\) i.e
\begin{equation} 1+a+a^{2}+\ldots . .+a^{k-1}=\displaystyle \displaystyle \frac{a^{k}-1}{a-1} \end{equation} Now we will prove this is true, for \(n=k+1\)
i.e \[ 1+a+a^{2}+\ldots .+a^{k+1-1}=\displaystyle \displaystyle \frac{a^{k+1}-1}{a-1} \] The left hand side can be written as \[1+a+a^{2}+\ldots .+a^{k}\] \[=\left(1+a+a^{2}+\ldots \ldots+a^{k-1}\right)+a^{k}\] from (1) we have \[=\displaystyle \displaystyle \frac{a^{k}-1}{a-1}+a^{k}\] taking LCM and re arranging we get \[= \displaystyle \frac{a^{k}-1+a^{k} \cdot a-a^{k}}{a-1}\] \[=\displaystyle \displaystyle \frac{a^{k+1}-1}{a-1}\] which is equal to right hand side of
So this is true by mathematical induction .
Question 3: Using induction prove that \[2^{n} \geq 2 n \; \forall n\; \geq 1\]
Solution : For \(n=1\), we have
\[2^{1} \geq 2 \]
equality holds, so above is true for \(n=1\)
let the statement is true, so taking \( n=k\),i.e \[2^{k} \geq 2 k\] For \(n=k+1\), we have have to show that
\[2^{k+1} \geq 2(k+1) \] Solving Left hand side \[=2^{k} \cdot 2^{1} \geq 2 k \cdot 2\] \[=4 k \] \[=2 k+2 k \] \[ \geq 2 k+2 \] \[=2(k+1)\] so form above we have \[2^{k+1} \geq 2(k+1)\] Hence statement is true for \(n=k+1\)
let the statement is true, so taking \( n=k\),i.e \[2^{k} \geq 2 k\] For \(n=k+1\), we have have to show that
\[2^{k+1} \geq 2(k+1) \] Solving Left hand side \[=2^{k} \cdot 2^{1} \geq 2 k \cdot 2\] \[=4 k \] \[=2 k+2 k \] \[ \geq 2 k+2 \] \[=2(k+1)\] so form above we have \[2^{k+1} \geq 2(k+1)\] Hence statement is true for \(n=k+1\)
Question 4: Use the principle of mathematical induction to prove that \[ 1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\displaystyle \displaystyle \frac{n^{2}(n+1)^{2}}{4} \quad \forall n \in \mathbb{N} \]
Solution: We have to prove that
\[
1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\displaystyle \displaystyle \frac{n^{2}(n+1)^{2}}{4}
\]
For \(\quad n=1\)
L.H.S. \(=1^{3}=1\)
R.H.S. \(=\displaystyle \displaystyle \frac{1^{2}(1+1)^{2}}{4}=\displaystyle \displaystyle \frac{1 \times 4}{4}=1\)
Therefor L.H.S.=R.H.S.
\(\therefore\) result (1) is true for \(n=1\).
Assume that (1) is true for \(n=k\)
\[ 1^{3}+2^{3}+3^{3}+\ldots+k^{3}=\displaystyle \displaystyle \frac{k^{2}(k+1)^{2}}{4} \] for \(n=k+1\), we have \begin{align} 1^{3}+2^{3}+\ldots+k^{3}+(k+1)^{3}=&\displaystyle \frac{k^{2}(k+1)^{2}}{4}\\ &+(k+1)^{3} \end{align} \[\hspace{2cm}=(k+1)^{2}\left[\displaystyle \displaystyle \frac{k^{2}+4 k+4}{4}\right] \] \[1+2^{3}+\ldots+(k+1)^{3}=\displaystyle \frac{(k+1)^{2}(k+2)^{2}}{4}\] This shows that result is true for \(n=k+1\).
L.H.S. \(=1^{3}=1\)
R.H.S. \(=\displaystyle \displaystyle \frac{1^{2}(1+1)^{2}}{4}=\displaystyle \displaystyle \frac{1 \times 4}{4}=1\)
Therefor L.H.S.=R.H.S.
\(\therefore\) result (1) is true for \(n=1\).
Assume that (1) is true for \(n=k\)
\[ 1^{3}+2^{3}+3^{3}+\ldots+k^{3}=\displaystyle \displaystyle \frac{k^{2}(k+1)^{2}}{4} \] for \(n=k+1\), we have \begin{align} 1^{3}+2^{3}+\ldots+k^{3}+(k+1)^{3}=&\displaystyle \frac{k^{2}(k+1)^{2}}{4}\\ &+(k+1)^{3} \end{align} \[\hspace{2cm}=(k+1)^{2}\left[\displaystyle \displaystyle \frac{k^{2}+4 k+4}{4}\right] \] \[1+2^{3}+\ldots+(k+1)^{3}=\displaystyle \frac{(k+1)^{2}(k+2)^{2}}{4}\] This shows that result is true for \(n=k+1\).
Question 5: Use Mathematicat Induction to show that \[ 1+2+4+\ldots .2^{n}=2^{n+1}-1 \]
Solution: Let us make the sries in power of \(2\), i.e
\[1+2+4 \ldots \ldots 2^{n}=2^{n+1}-1 \]
\[2^{0}+2^{1}+2^{2} \ldots \ldots 2^{n}=2^{n+1}-1\]
First we show that result is true, for \(n=1\)
\[
2^{0}+2^{1}=2^{1+1}-1 \]
\[3=3\]
LHS=RHS, so given result is true for \(n=1\)
Let us suppose that given statement is true, for \(n=k\), i.e \[ 2^{0}+2^{1}+2^{2} \ldots 2^{k}=2^{k+1}-1 \] Now we will prove that statement is true, for \(n=k+1\)
so put \(n=k+1\) in (1) \[ 2^{0}+2^{1}+2^{2} \ldots 2^{k}+2^{k+1}=2^{k+2}-1 \] \[2^{0}+2^{1}+\cdots +2^{k}+2^{k+1} \] \[=\left(2^{0}+2^{1}+\ldots+2^{k}\right)+2^{k+1} \] \[=2^{k+1}-1+2^{k+1} \] \[=2^{k+1}+2^{k+1}-1 \] \[=2^{k+2}-1 \] we get LHS=RHS , so the given statemnet is true for all \(n\)
Hence \(\mathrm{P}(n)\) is true by Induction.
Let us suppose that given statement is true, for \(n=k\), i.e \[ 2^{0}+2^{1}+2^{2} \ldots 2^{k}=2^{k+1}-1 \] Now we will prove that statement is true, for \(n=k+1\)
so put \(n=k+1\) in (1) \[ 2^{0}+2^{1}+2^{2} \ldots 2^{k}+2^{k+1}=2^{k+2}-1 \] \[2^{0}+2^{1}+\cdots +2^{k}+2^{k+1} \] \[=\left(2^{0}+2^{1}+\ldots+2^{k}\right)+2^{k+1} \] \[=2^{k+1}-1+2^{k+1} \] \[=2^{k+1}+2^{k+1}-1 \] \[=2^{k+2}-1 \] we get LHS=RHS , so the given statemnet is true for all \(n\)
Hence \(\mathrm{P}(n)\) is true by Induction.
Question 6: Use the principle of mathematical induction to prove that \[ 1.3+2.4+\ldots+n(n+2)= \frac{n(n+1)(2 n+7)}{6}\\ \forall \quad n \in \mathrm{N} \]
Solution: We have to prove that
\[
1.3+2.4+\ldots+n(n+2)=\displaystyle \displaystyle \frac{n(n+1)(2 n+7)}{6}
\]
when \(n=1\)
L.H.S. \(=1.3=3\)
R.H.S. \(=\displaystyle \frac{1(1+1)(2+7)}{6}=\displaystyle \displaystyle \frac{1 \times 2 \times 9}{6}=3\)
LHS=RHS
result \((1)\) is true for \(n=1\). Assume that result (1) is true for \(n=k\). i.e \[1.3+2.4+\ldots+k(k+2)=\displaystyle \frac{k(k+1)(2 k+7)}{6} \] in above equation add \((k+1)(k+3)\) to both sides, we get, \[1.3+2.4+\ldots+k(k+2)+(k+1)(k+3)\] \[\hspace{2cm}=\displaystyle \displaystyle \frac{k(k+1)(2 k+7)}{6}+(k+1)(k+3)\] \[ =(k+1)\left[\displaystyle \displaystyle \frac{k(2 k+7)}{6}+k+3\right]\] \[=(k+1)\left[\displaystyle \displaystyle \frac{k(2 k+7)+6 k+18}{6}\right]\] \[=(k+1)\left[\displaystyle \displaystyle \frac{(k+2)(2 k+9)}{6}\right] \] \begin{align} \quad 1.3+2.4+\ldots+(k+1)(k+3) &\\ =\displaystyle \frac{(k+1)(k+2)(2 k+9)}{6} \end{align} so the result is true for \(n=k+1\). \(\therefore\) by method of induction, result (1) is true for all \(n \in \mathbf{N}\).
L.H.S. \(=1.3=3\)
R.H.S. \(=\displaystyle \frac{1(1+1)(2+7)}{6}=\displaystyle \displaystyle \frac{1 \times 2 \times 9}{6}=3\)
LHS=RHS
result \((1)\) is true for \(n=1\). Assume that result (1) is true for \(n=k\). i.e \[1.3+2.4+\ldots+k(k+2)=\displaystyle \frac{k(k+1)(2 k+7)}{6} \] in above equation add \((k+1)(k+3)\) to both sides, we get, \[1.3+2.4+\ldots+k(k+2)+(k+1)(k+3)\] \[\hspace{2cm}=\displaystyle \displaystyle \frac{k(k+1)(2 k+7)}{6}+(k+1)(k+3)\] \[ =(k+1)\left[\displaystyle \displaystyle \frac{k(2 k+7)}{6}+k+3\right]\] \[=(k+1)\left[\displaystyle \displaystyle \frac{k(2 k+7)+6 k+18}{6}\right]\] \[=(k+1)\left[\displaystyle \displaystyle \frac{(k+2)(2 k+9)}{6}\right] \] \begin{align} \quad 1.3+2.4+\ldots+(k+1)(k+3) &\\ =\displaystyle \frac{(k+1)(k+2)(2 k+9)}{6} \end{align} so the result is true for \(n=k+1\). \(\therefore\) by method of induction, result (1) is true for all \(n \in \mathbf{N}\).
Example 7 : Use the principle of mathematical induction to prove that \begin{align} \displaystyle \frac{1}{1.3}+\displaystyle \displaystyle \frac{1}{3.5}+ \ldots+\displaystyle \frac{1}{(2n-1)(2n+1)}\\ =\displaystyle \frac{n}{2n+1} \end{align}
Solution: We have to prove that
\begin{align}
\displaystyle \frac{1}{1.3}+\displaystyle \displaystyle \frac{1}{3.5}+ \ldots+\displaystyle \frac{1}{(2n-1)(2n+1)}\\
=\displaystyle \frac{n}{2n+1}
\end{align}
For \(n=1\),
\begin{aligned}
\text { L.H.S. }=\displaystyle \displaystyle \frac{1}{1 \cdot 3}=\displaystyle \displaystyle \frac{1}{3} \\
\text { R.H.S. }=\displaystyle \displaystyle \frac{1}{2+1}=\displaystyle \displaystyle \frac{1}{3}
\end{aligned}
therefore LHS=RHS
result \((1)\) is true for \(n=1\)
Assume that result (1) is true for \(n=k\). \begin{align} \displaystyle \frac{1}{1.3}+\displaystyle \frac{1}{3.5}+\ldots+ \displaystyle \frac{1}{(2 k-1)(2 k+1)}\\ = \displaystyle \frac{k}{2 k+1} \end{align} let Adding \(\displaystyle \frac{1}{(2 k+1)(2 k+3)}\) to both sides, we will get \[\displaystyle \frac{1}{1.3}+\displaystyle \frac{1}{3.5}+\ldots+ \displaystyle \frac{1}{(2 k-1)(2 k+1)}+\displaystyle \frac{1}{(2 k+1)(2 k+3)}= \displaystyle \frac{k}{2 k+1}+\displaystyle \frac{1}{(2 k+1)(2 k+3)}\] \(=\displaystyle \frac{1}{2 k+1}\left[\displaystyle \frac{(k+1)(2 k+1)}{2 k+3}\right]\) \[ \displaystyle \frac{1}{1.3}+ \displaystyle \frac{1}{3.5}+\ldots \displaystyle+\displaystyle \frac{1}{(2k+1)(2 k+3)}=\displaystyle \frac{k+1}{2 k+3} \] Comparing this result with result (1), we see that result (1) is true for \(n=k+1\)
by method of induction, the result is true for all natural numbers \(n\).
Example 8 : Using Mathematical Induction prove that
\[
a+a r+a r^{2} \ldots \ldots . a r^{n-1}=\displaystyle \displaystyle \frac{a\left(1-r^{n}\right)}{1-r}, r \neq 0
\]
Solution: For \(n=1\)
\[
\begin{aligned}
ar^{1-1} =\displaystyle \displaystyle \frac{a\left(1-r^{1}\right)}{1-r} \\
a=a
\end{aligned}
\]
Result is True for \(n=1\)
Let the result is true for \(n=k\), i.e
\[ a+a r+a r^{2} \ldots \ldots .+a r^{k}= \displaystyle \frac{a\left(1-r^{k}\right)}{1-r}, r \neq 0 \] For \(n=k+1\), we have
\[ a+a r+a r^{2} \ldots +a r^{k}= \displaystyle \frac{a\left(1-r^{k+1}\right)}{1-r} \] L.H.S. \[=a+a r+a r^{2} \ldots \ldots . .+a r^{k}\] we can we write above as \[ =a+a r+a r^{2} \ldots \ldots . . a r^{\mathrm{k}-1}+a r^{\mathrm{k}} \] from (2) we have \[=a \displaystyle \displaystyle \frac{\left(1-r^{k}\right)}{1-r}+a r^{k}\] \[=a\left[\displaystyle \frac{1-r^{k}+r^{k}-r^{k+1}}{1-r}\right]\] \[=a\left[\displaystyle \frac{1-r^{k+1}}{1-r}\right]\] above is same as R.H.S
So result is True for \(n=k+1\)
Let the result is true for \(n=k\), i.e
\[ a+a r+a r^{2} \ldots \ldots .+a r^{k}= \displaystyle \frac{a\left(1-r^{k}\right)}{1-r}, r \neq 0 \] For \(n=k+1\), we have
\[ a+a r+a r^{2} \ldots +a r^{k}= \displaystyle \frac{a\left(1-r^{k+1}\right)}{1-r} \] L.H.S. \[=a+a r+a r^{2} \ldots \ldots . .+a r^{k}\] we can we write above as \[ =a+a r+a r^{2} \ldots \ldots . . a r^{\mathrm{k}-1}+a r^{\mathrm{k}} \] from (2) we have \[=a \displaystyle \displaystyle \frac{\left(1-r^{k}\right)}{1-r}+a r^{k}\] \[=a\left[\displaystyle \frac{1-r^{k}+r^{k}-r^{k+1}}{1-r}\right]\] \[=a\left[\displaystyle \frac{1-r^{k+1}}{1-r}\right]\] above is same as R.H.S
So result is True for \(n=k+1\)
Question 9: Using mathematical induction prove that \[1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\displaystyle \frac{n^{2}(n+1)^{2}}{4}\]
Solution : For \(n=1\) we have
\[1^3=\displaystyle \frac{1(2)^2}{4}\]
so from above we have
\[1=1\]
\[L.H.S = R.H.S\]
Assume that result (1) is true for \(n=k\)
\[1^{3}+2^{3}+3^{3}+\ldots+k^{3}=\displaystyle \frac{k^{2}(k+1)^{2}}{4}\]
For \(n=k+1\), we have
\begin{align}
&1^{3}+2^{3}+\ldots+k^{3}+(k+1)^{3}=\displaystyle \frac{k^{2}(k+1)^{2}}{4}\\
&+(k+1)^{3}
\end{align}
using (1) , and re-arranging above we get,
\[=(k+1)^{2}\left[\displaystyle \frac{k^{2}}{4}+(k+1)\right]\]
\[=(k+1)^{2}\left[\displaystyle \frac{k^{2}+4 k+4}{4}\right]\]
\[1^{3}+\ldots+k^{3}+(k+1)^{3}= \frac{(k+1)^{2}(k+2)^{2}}{4}\]
which by comparison with result (1) shows that result is true for \(n=k+1\).
\(\therefore\) by method of induction, result (1) is true for all \(n \in \mathrm{N}\).
\(\therefore\) by method of induction, result (1) is true for all \(n \in \mathrm{N}\).
Example 10 : Prove that for any positive integer \(n\), then number \(2^{3 n}-1\) is divisible by 7
Solution : First lets see is this true for \(n=1\)
put \(n=1\) in (1), we will get
\[2^{3.1}-1=7\;\;\;\;\text{is divisible by 7}\] so the result is true forn \(n=1\)
let us Suppose that (1) is true. for \(n=k\), i.e\(\;\; 2^{3 k}-1\) is divisible by 7
or we can say that
\[2^{3 k}-1=7 p \text {, where } p \text { is a positive integer. } \] \[\Rightarrow 2^{3 k}=7 p+1\] which is divisible by \(7 .\)
Lets take \(n=k+1\), in (1), we will get
\[ 2^{3k+3}-1\] \[ 2^{3k+3}-1=2^{3k} \times 2^3-1\] \[ =2^{3k} \times8-1\] from (2) we have
\[ =(7p+1)8-1\] \[ 56p+7\] Taking out common \(7\), we get
\[ 56p+7=7(8p+1)\] as this is very clear that above is multiple of 7, so it will be divisible by 7.
The result is true for \(n=k+1\).
Hence (1) is true for all \(n\).
Example 11 : Prove that \(a-b\) divides \(a^{n}-b^{n}\) for \(n \geq 1\).
Solution: First we show that statement is true for \(n=1\)
\(a-b\) divides \(a^{1}-b^{1}\), which is true.
Suppose that (1) is true for \(n=k\), from this we will have
\[a^{k}-b^{k}=p(a-b) \text{where p is an integer}\]. \[a^{k}=p(a-b)+b^{k}\] Now we prove the statement is true for \(n=k+1\), i.e \[a-b \;\;\text{divides}\;\; a^{k+1}-b^{k+1}\] re-arranging terms in \(a^{k+1}-b^{k+1}\), we have \[a^{k+1}-b^{k+1}=a^{k} \cdot a-b^{k+1}\] \[ \begin{aligned} =\left[p(a-b)+b^{k}\right] \cdot a-b^{k+1} \\ =p(a-b) \cdot a+b^{k} \cdot a-b^{k+1} \\ =p(a-b) a+b^{k} \cdot a-b^{k} \cdot b \\ =p(a-b) a+b^{k}(a-b) \\ =(a-b)\left[p a+b^{k}\right] \end{aligned} \] which is divisible by \(a-b\). Hence by mathematical induction \(a-b\) divides \(a^{n}-b^{n}\) for \(n \geq 1\).
Example 12 : Using Mathematical Induction Prove that \(n^{3}+3 n^{2}+5 n+3\) is divisible by 3.
Solution: For \(n=1\), we have \[1^3+3.1^2+5+3=12\]
which is divisible by 3, result is true for \(n=1\).
Assume that the result is true for \(n=k\), i.e \[ k^{3}+3 k^{2}+5 k+3\] so we will have \[k^{3}+3 k^{2}+5 k+3=3 m\] where \(m\) is an integer Now we will prove that result is true for \(n=k+1\), i.e \begin{align} &=(k+1)^{3}+3(k+1)^{2}+5(k+1)+3 \\ &=\left(k^{3}+3 k^{2}+3 k+1\right)+3\left(k^{2}+2 k+1\right)\\ &+(5 k+5)+3 \\ &=\left(k^{3}+3 k^{2}+5 k+3\right)+\left(3 k^{2}+9 k+9\right) \\ &=3m+3\left(k^{2}+3 k+3\right) \\ &=3\left[m+\left(k^{2}+3 k+3\right)\right] \end{align} which is divisible by 3 .
\(\therefore\) result is true for \(n=k+1\).
Assume that the result is true for \(n=k\), i.e \[ k^{3}+3 k^{2}+5 k+3\] so we will have \[k^{3}+3 k^{2}+5 k+3=3 m\] where \(m\) is an integer Now we will prove that result is true for \(n=k+1\), i.e \begin{align} &=(k+1)^{3}+3(k+1)^{2}+5(k+1)+3 \\ &=\left(k^{3}+3 k^{2}+3 k+1\right)+3\left(k^{2}+2 k+1\right)\\ &+(5 k+5)+3 \\ &=\left(k^{3}+3 k^{2}+5 k+3\right)+\left(3 k^{2}+9 k+9\right) \\ &=3m+3\left(k^{2}+3 k+3\right) \\ &=3\left[m+\left(k^{2}+3 k+3\right)\right] \end{align} which is divisible by 3 .
\(\therefore\) result is true for \(n=k+1\).
Question 13 : Prove by mathematical induction that \(3^{4 n+1}+2^{2 n+2} \text { is divisible by } 7\)
Solution : When \(n=1\), we have \[3^{4}+1+2^{2+2}=3^{5}+2^{4}=243+16 =7 \times 37\] \text {which is divisible by } 7
Let result is true for \(n=k\), i.e
\[ 3^{4 k+1}+2^{2 k+2}=7m \text { where } m \text { is an integer. } \] re-arranging above we will get \[ 3^{4 k+1}=7m-2^{2 k+2}\] For \(n=k+1\) we have \[3^{4(k+1)+1}+2^{2(k+1)+2} =3^{4 k+1} \cdot 3^{4}+2^{2 k+2} \cdot 2^{2}\] \[=81.3^{4 k+1}+4.2^{2 k+2}\] \[=81\left(7 m-2^{2 k+2}\right)+4.2^{2 k+2} \quad[\therefore \text { of (1)] }\] \[=7.81 m-77.2^{2 k+2} \] \[=7\left(81 m-11.2^{2 k+2}\right), \text { which is a multiple of } 7 .\] \(\therefore\) result is true for \(n=k+1\) \(\therefore\) by method of induction, the result is true for all \(n\)
Example 14 : Prove that \(10^{2 n-1}+1\) is divisible by 11
Solution : Put \(n=1\) \[10^{2 \cdot 1-1}+1 =11 \] \[\text { which is divisible by } 11\]
Let result is true for \(n=k\), i.e
\[ 10^{2 k-1}+1 \text { is divisible by } 11 \] \[\quad 10^{2 k-1}+1=11 m \] \[10^{2 k-1}=11 m-1 \] \(\text Put\; n=k+1\)
\[10^{2(k+1)-1}+1=10^{2 k+2-1}+1 \] \[10^{2 k-1} 10^{2}+1=(11 m-1) 100+1 \] \[=1100 m-100+1 \] \[=1100 m-99 \] \[=1100m-99 \] \[=11(100 \mathrm{~m}-9) \text { which is divisible by } 11 \] Hence the statement is true for any \(n \in \mathbf{N}\)
Example 15 : Prove by using induction that \[4^{k+1}+5^{2k-1}\] is divisible by \(21\)
Solution : For \(n=1\), we have \[ \begin{aligned} & 4^{1+1}+5^{2.1-1}=4^{2}+5^{1} \\ & =16+5 \\ &=21 \text { which is true. } \end{aligned} \] Let result is true for \(n=k\), i.e \[ 21 \text { divides } 4^{k+1}+5^{2 k-1} \] so we can write above as \[ 4^{k+1}+5^{2 k-1}=21 m \] where \(m\) is some positive integer.
by re-arranging the terms we get, \begin{align} & 4^{k+1}+5^{2 k-1}=21 m \\ & 5^{2 k-1}=21 m-4^{k+1} \end{align}
for \(n=k+1\), we have \[ \begin{aligned} &=4^{k+2} +5^{2k+1} \\ &=4^{k+2} +25 \cdot 5^{2k-1} \\ &=4^{k+1}\cdot 4 +(21 m -4^{k+1}) \cdot 25 \\ &=4^{k+1}(4-25)+21 m \cdot 25 \\ &=4^{k+1}(-21)+21 m \cdot 25 \\ &=21\left(-4^{k+1}+25 m\right) \end{aligned} \] \text { which is divisible by } 21
so the statemnet is true for \(k+1\), hence the statement is true for all \(n \in \mathbf{N}\).
0 Comments