Second Principle of Mathematical Induction

Second Principle of Mathematical Induction
Let  
\[P(n)\]
  be a proposition depending on an integer  
\[n\]
. If
1.  
\[P(n_0)\]
  is true for some integer  
\[n_0\]

2. For  
\[k \gt n_0\]
   
\[P(n_0), \; P(n_0+1), \; P(n_0+2),..., \; P(k)\]
  are true
then  
\[P(n)\]
  is true for all  
\[n \gt n_0\]
.
Example: Let  
\[x_0 =1, \; x_n=x_0+x_1+...x_{n-1}\]
  and let  
\[P(n)\]
  be the proposition that  
\[x_n=2^{n-1}\]
.
\[x_1=x_0=1=2^{1-1}\]
  so  
\[P(1)\]
  is true.
Suppose that  
\[P(1), \; P(2),...,P(k)\]
  are all true.
\[\begin{equation} \begin{aligned} x_{k+1} &= x_0+x_1+x_2+...x_k \\ &=1+ 2^{1-1}+2^{2-1}2^{3-1}+...+2^{k-1} \\ &= 1+1+2+4+...2^{k-1}=1+ \frac{1(1-2^k)}{1-2} \\ &= 2^k \end{aligned} \end{equation}\]

Hence  
\[P(k+1)\]
  is true so proposition is proved.