Principle of Mathematical Induction

Principle of Mathematical Induction

Steps :

To apply principle of mathematical induction to a statement Pn :

1. Write out the statements P₁, P_k, P_k+1

2. Show that P₁ is true.

3. Assuming P_k is true, show that the truth of P_k+1 follows (induction step).

4. Conclude that Pn holds for all 'n'.

Standard Conclusion : Since P1 is true and P_k => P_k+1 , the statement is true by induction.

Type 1

Prove the statement  $1+2+3...+n=\frac{1}{2}n\left(n+1\right)\$  .

Let Pn be the statement  $1+2+3+....n\ =\frac{1}{2}n\left(n+1\right)$  
 $P_1:1=\frac{1}{2}\left(1\right)\left(1+1\right)$  
 $P_k:1+2+3+...+k=\frac{1}{2}k\left(k+1\right)$   $P_{k+1}:\ 1\ +\ 2\ +3\ +...\ +\left(k+1\right)=\frac{1}{2}\left(k+1\right)\left(k+1+1\right)$                                                                                                                                        $=\frac{1}{2}\left(k+1\right)\left(k+2\right)$  
 $P_1\ is\ true\$  since  $\frac{1}{2}\left(1\right)\left(1+1\right)=\frac{1}{2}\left(2\right)=1$  
Assume Pk is true .
Consider Pk+1 
 $1+2+3+...+\left(k+1\right)$  
 $=1+2+3+...\ +k\ +\left(k+1\right)$  
 $=\frac{1}{2}k\left(k+1\right)+k+1\$  

continued

 $=\frac{k\left(k+1\right)}{2}+k+1$  
 $=\frac{k^{2\ }+k+2\left(k+1\right)}{2}$  
 $=\frac{k^2+k+2k+2}{2}$  
 $=\frac{k^2+3k+2}{2}$  
 $=\frac{\left(k+1\right)\left(k+2\right)}{2}$  
 $=\frac{1}{2}\left(k+1\right)\left(k+2\right)$  
 $P_k=>P_{k+1}$  
Since P1 is true and Pk => Pk+1 , the statement is true by induction. 

Type 2

Prove the statement  $\sum_{r=1}^n\left(2+3r\right)=\frac{1}{2}n\left(3n+7\right)$  
Let Pn be the statement  $\sum_{r=1}^n\left(2+3r\right)=\frac{1}{2}n\left(3n+7\right)$  
 $P_1:\ 2+3\left(1\right)=\frac{1}{2}\left(1\right)\left(3\left(1\right)+7\right)$  
 $P_k:\ \sum_{r=1}^k\left(2+3r\right)=\frac{1}{2}k\left(3k+7\right)$  
 $P_{k+1}:\ \sum_{r=1}^{k+1}\left(2+3r\right)=\frac{1}{2}\left(k+1\right)\left(3\left(k+1\right)+7\right)$                                                                         
 $=\frac{1}{2}\left(k+1\right)\left(3k+10\right)$  
 $P_1\ is\ true\$  since 2 + 3 = 1/2 (10) = 5.
Assume Pk is true.
Consider Pk+1.
 $\sum_{r=1}^{k+1}\left(2+3r\right)=\ sum\ of\ 1st\ 'k'\ terms\ +\ \left(k+1\right)th\ term$  

CONTINUED

 $=\sum_{r=1}^k\left(2+3r\right)+\left(2+3\left(k+1\right)\right)$  
 $=\frac{1}{2}k\left(3k+7\right)+\left(5+3k\right)$  
 $=\frac{3k^2+7k}{2}+\left(5+3k\right)$  
 $=\frac{3k^2+7k+2\left(5+3k\right)}{2}$  
 $=\frac{3k^2+7k+10+6k}{2}$  
 $=\frac{3k^2+13k+10}{2}$  
 $=\frac{\left(k+1\right)\left(3k+10\right)}{2}$  
 $=\frac{1}{2}\left(k+1\right)\left(3k+10\right)$  
Since  P1 is true and Pk => Pk+1 , the statement is true by induction. 

Type 3- Induction Applied to Divisibility 

 Prove that  $7^n-2^n$  is divisible by 5 for all positive intergers.

Let Pn be the statement  $7^n-2^n$  is divisible by 5  $\forall$  n  $\in Z^+$  .
 $P_1:\ 7^{1\ }-2^1\ is\ divisible\ by\ 5.$  
 $P_k:\ 7^k-2^kis\ divisible\ by\ 5.$  
 $P_{k+1}:\ 7^{k+1}-2^{k+1}is\ divisible\ by\ 5.$  

P1 is true since 7 - 2 = 5 which is divisible by 5. 
Assume Pk is true. 
 $\Longrightarrow7^k-2^k=5a\ ,\ a\in Z^+$  
 $\Longrightarrow7^k=5a+2^k$  
Consider Pk+1
 $=7^{k+1}-2^{k+1}$                                       $=5\left(7a+2^k\right)$  
 $=\left(7^k\right)\left(7^1\right)-2^{k+1}$                             $=5b\ ,b=7a+2^k\in Z^+$  
 $=7\left(7^k\right)-2^{k+1}$                                $\therefore P_k=>\ P_{k+1}$  
 $=7\left(5a+2^k\right)-2^{k+1}$        Since P1 is true and Pk=> Pk+1 , the stament is true by induction. 
 $=35a+7\left(2^k\right)-2\left(2^k\right)$  
 $=35a+5\left(2^k\right)$  

Type 4 - Induction applied to Inequalities

Prove that  $2^n>n\ ,\ n\ \in Z^+$  

Let Pn be the statement  $2^{n\ }>n\ ,\forall n\in Z^+$  
 $P_1:\ 2^1>1$  
 $P_k:\ 2^{k\ }>k$  
 $P_{k+1}:\ 2^{k+1}>k+1$  
P1 is true since  is 2 which is greater than 1. 
Assume Pk is true. 
Consider Pk+1.
 $2^k>k$  (building from the Pk )
 $\left(\times2\right)\ 2\left(2^k\right)>2k$  
 $2^{k+1}>2k$  
 $2^{k+1}>k+k$  
 $But\ k\ge1$  (+ve Z)
 $2^{k+1}>k+1$  
 $\therefore P_k=>P_{k+1}$  
P1 is true and Pk =. Pk+1 therefore the statement is true by induction. 
(Note : when k is more than or equal to 1 the the statement remains true if one of the k's is replaced by 1.