The Principle of Mathematical Induction

Statement of the principle. Let $P(n)$ be a statement (a mathematical assertion) involving the natural number $n$. Suppose the following two conditions both hold:

1. Base case (basis step). $P(1)$ is true, i.e. the statement holds for $n = 1$.
2. Inductive step. For every natural number $k \ge 1$, if $P(k)$ is true then $P(k+1)$ is also true. That is, $P(k) \Rightarrow P(k+1)$ for every $k \ge 1$.

Then $P(n)$ is true for every natural number $n \ge 1$.

Reading the inductive step correctly. The inductive step does not ask you to prove $P(k)$ -- it asks you to prove the implication $P(k) \Rightarrow P(k+1)$. You are allowed, indeed required, to assume $P(k)$ is true (this assumption is called the inductive hypothesis) and use it as one of your tools to establish $P(k+1)$. Proving the implication for an arbitrary but fixed $k$ is what lets the base case propagate all the way up the ladder of natural numbers: $P(1)$ true and $P(1)\Rightarrow P(2)$ give $P(2)$ true; $P(2)$ true and $P(2) \Rightarrow P(3)$ give $P(3)$ true; and so on, without end.

Why both steps are essential. Neither step alone is sufficient. If only the base case is verified, we know nothing beyond $P(1)$ -- the statement could easily fail at $n=2$. If only the inductive step is verified (i.e. $P(k) \Rightarrow P(k+1)$ is shown for all $k$) but the base case is skipped, the chain of implications has nothing to start from, and $P(n)$ could be false for every $n$: the assertion $n = n+1$ satisfies the inductive-step form (add $1$ to both sides of the assumption) but is false for every natural number, precisely because its base case, $1 = 2$, fails. …