Let
\[P(n)\]
be a proposition depending on an integer \[n\]
. If1.
\[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 truethen
\[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.