The starting point of mathematical induction is generally 1.
It could also be zero or a positive integer or a negative
It is required to prove that P(k) ⇒ P(k + 1).
Therefore, proving a statement using the principle of mathematical induction involves 3 steps below :
i) Basis of induction : Show that P(1) is true.
ii) Inductive hypothesis : For k ≥ 1, assume P(k) is true.
iii) Inductive step : Prove that P(k + 1) is true
The first two steps above (Basis of induction and Inductive hypothesis) are crucial. Careless use can lead to some absurd conclusions there are statements that are true for many natural numbers but not for all of them (as in the example below)
Example 1 :
The formula P(n) = n2 – n + 41 gives a prime numbers for n = 1, 2, 3, ... , 40.
But P(41) = 412 is obviously divisible by 41. Therefore, it is not a prime number.
Example 2 :
For n ∈ N, let P(n) be the statement
" 1 + 2 + 3 + ... + (2n – 1) = n2 + (n – 1) (n – 2) ... (n – 10)"
Then P(1), P(2), ... , P(10) are all true.
But P(11) is not true.