Principle of Induction (Generalised)
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(k)\]
is truethen
\[P(n)\]
is true for all \[n \gt n_0\]
.Note that the definition does not imply that
\[P(n)\]
is always true, only that it is true from some integer onwards. Consider the statement 'square numbers are bigger than 5' which is false for \[1^2 =1, \; 2^2=4\]
but greater for other square numbers. The correct statement would be 'if \[n gt 2\]
the \[n^{th}\]
square number is greater than 5'. We could take \[n_0=3\]
and use induction to prove the sediment in the following way:\[P(3)=3^2 \gt 5\]
so \[P(3)\]
is true.Suppose then that
\[P(k)\]
is true and prove \[P(k+1)\]
is true.\[(k+1)^2 =k^2+2k+1 \gt k^2 \gt 5\]
so \[P(k+1)\]
is true and the proposition is true for \[n \gt 2\]
. 
