## Principle of Induction (Generalised)

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(k)$
is true
then
$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$
.