## 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\]

.