Base case and inductive step

The problem that induction solves

How do you prove that a property P(n) is true for ALL natural numbers n from a certain rank onwards, when there are infinitely many of them? You obviously cannot check each case one by one. Proof by induction answers this problem in just two steps.

The two mandatory steps

Principle of induction for a property P(n):

Step 1 - BASE CASE
  We check that P(n0) is true            (n0 = the first rank, often 0 or 1)

Step 2 - INDUCTIVE STEP
  We assume P(k) is true for some k >= n0  (induction hypothesis)
  We then prove that P(k+1) is true        (the next step)

CONCLUSION: P(n) is true for all n >= n0

Why these two steps are enough

The base case gives a solid starting point (P(n0) is true). The inductive step shows that the truth is automatically passed on from one rank to the next, whatever that rank is. Combining the two: P(n0) is true, so P(n0+1) is true (by the inductive step), so P(n0+2) is true, and so on indefinitely. The property propagates to infinity without needing to be checked rank by rank.

What must be well understood in the inductive step

The inductive step does NOT prove that P(k) is true: it only proves an implication, "IF P(k) is true THEN P(k+1) is true". This is an essential difference: we never assume the property is true in general, only that it is true at ONE fixed rank k, in order to deduce the next rank.

Common pitfall

Both steps are essential: the inductive step alone, without a checked base case, proves nothing at all (see the lesson on classic mistakes). An implication "P(k) true implies P(k+1) true" can be perfectly correct and yet start from no initial truth, in which case it proves absolutely nothing about actual integers.