Some statements in mathematics are claimed to hold for every natural number $n$ — for instance "$1+2+\cdots+n = \dfrac{n(n+1)}{2}$" or "$2^n > n$". You cannot check infinitely many cases one by one, and verifying the first few cases proves nothing on its own. Mathematical induction is the tool built precisely for this: it lets a finite argument establish an infinite family of statements.
Write $P(n)$ for the statement about the natural number $n$. The Principle of Mathematical Induction (PMI) says:
$$\text{If } P(1) \text{ is true, and } \big(P(k) \Rightarrow P(k+1)\big) \text{ for every } k \ge 1, \text{ then } P(n) \text{ is true for all } n \in \mathbb{N}.$$
A proof therefore has exactly two parts:
- Base case (basis step): show $P(1)$ is true — the statement holds at the starting value.
- Inductive step: assume $P(k)$ is true for an arbitrary fixed $k \ge 1$ (this assumption is the inductive hypothesis), and use it to prove $P(k+1)$.
The domino / ladder intuition. Picture an infinite line of dominoes. The base case is knocking over the first domino. The inductive step is the guarantee that whenever a domino falls it topples the next one. With both facts in place, every domino must fall. Climbing a ladder is the same idea: you can reach the first rung (base case), and from any rung you can step to the next (inductive step), so you can reach every rung.
Why both steps are essential — neither alone is enough. The inductive step alone is a "chain reaction with no spark": it shows each statement would follow from the previous one, but if the first never holds, the chain never starts. For example $P(n):$ "$n = n+1$" satisfies a (false) inductive style of reasoning in spirit but has no true base case, so it proves nothing. Conversely, the base case alone proves only the single statement $P(1)$. A notorious trap is the claim "$n^2 + n + 41$ is prime": it is prime for $n = 0, 1, 2, \dots, 39$, yet fails at $n = 40$ (giving $41^2$). Checking many cases is not a proof — only the inductive step turns finitely much work into a statement about all $n$.
The skeleton of every induction proof. Lay it out the same way each time so no part is skipped:
The decisive move in step 4 is almost always to relate $P(k+1)$ back to $P(k)$ — split off the new term, or factor out the previous case — so the inductive hypothesis can be substituted. If your proof of the inductive step never actually uses the assumption $P(k)$, you have probably not done induction at all.
Starting value need not be $1$. If a statement is claimed only for $n \ge n_0$, take the base case at $n = n_0$; everything else is unchanged. For instance $2^n > n^2$ is false at $n = 2,3,4$ but true for all $n \ge 5$, so its base case is $P(5)$.
Deeper Insight — induction is the natural numbers' defining property, not a trick. The set $\mathbb{N}$ is built so that you reach every number by starting at $1$ and repeatedly adding $1$; induction is simply that construction read as a proof method. This is why the inductive step must connect $k$ to $k+1$ specifically — it mirrors how the next natural number is generated. Seen this way, "assume it for $k$, prove it for $k+1$" is not circular reasoning (a common worry): you are not assuming what you want to prove, you are assuming one instance to derive the next instance, exactly as the dominoes pass the fall along. Master this single relate-$k$-to-$(k+1)$ habit and the summation, divisibility and inequality proofs that follow become variations on one theme.
For $P(n): 1 + 3 + 5 + \cdots + (2n-1) = n^2$, verify the base case $P(1)$.
Solution- Substitute $n = 1$ on the left: the sum has the single term $2(1)-1 = 1$.
- Right side at $n = 1$: $1^2 = 1$.
- Both sides equal $1$, so $P(1)$ holds.
Answer: $P(1)$ is true (LHS $= 1 =$ RHS), so the base case is established.
For the same $P(n): 1 + 3 + \cdots + (2n-1) = n^2$, write the inductive hypothesis and the statement $P(k+1)$ you must prove.
Solution- Hypothesis $P(k)$: assume $1 + 3 + \cdots + (2k-1) = k^2$ for some fixed $k \ge 1$.
- The $(k+1)$th odd term is $2(k+1)-1 = 2k+1$.
- To prove $P(k+1)$: $1 + 3 + \cdots + (2k-1) + (2k+1) = (k+1)^2$.
Answer: Hypothesis: $\sum_{i=1}^{k}(2i-1) = k^2$; target: $\sum_{i=1}^{k+1}(2i-1) = (k+1)^2$.
Complete the inductive step for $P(n): 1 + 3 + \cdots + (2n-1) = n^2$.
Solution- Start from the LHS of $P(k+1)$ and split off the last term: $\big[1 + 3 + \cdots + (2k-1)\big] + (2k+1)$.
- Apply the hypothesis to the bracket: $= k^2 + (2k+1)$.
- Recognise the perfect square: $k^2 + 2k + 1 = (k+1)^2$.
- This is exactly the RHS of $P(k+1)$.
Answer: $P(k) \Rightarrow P(k+1)$; with the base case, by PMI $1 + 3 + \cdots + (2n-1) = n^2$ for all $n \in \mathbb{N}$.
Explain why checking $P(1), P(2), P(3)$ alone does not prove $P(n)$ for all $n$.
Solution- Verifying finitely many cases confirms only those particular statements.
- A property can hold for the first several values and then fail: e.g. $n^2 - n + 41$ is prime for $n = 1, \dots, 40$ but composite at $n = 41$.
- Only the inductive step $P(k) \Rightarrow P(k+1)$ converts a finite argument into a claim about every $n$.
Answer: Spot-checking cannot cover infinitely many $n$; the inductive step is what makes the conclusion universal.
Identify the base case for a statement claimed to hold only for $n \ge 4$.
Solution- The starting value $n_0$ is the smallest $n$ for which the claim is asserted, here $n_0 = 4$.
- So the base case is $P(4)$, verified by direct substitution.
- The inductive step then runs for all $k \ge 4$.
Answer: The base case is $P(4)$; PMI then gives the result for all $n \ge 4$.
A "proof" shows $P(k) \Rightarrow P(k+1)$ for $P(n): n = n + 1$ but never checks a base case. What is wrong?
Solution- $P(n): n = n+1$ is false for every $n$, so no base case can be true.
- Even if an inductive step could be written, the chain never starts.
- Hence nothing is proved — the missing (and unprovable) base case is fatal.
Answer: Without a true base case the induction collapses; the statement is in fact false for all $n$.
Using induction, prove that $P(n): 1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.
Solution- Base: $n = 1$ gives LHS $= 1$ and RHS $= \dfrac{1\cdot 2}{2} = 1$. True.
- Hypothesis: assume $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$.
- Step: $1 + 2 + \cdots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = (k+1)\!\left(\dfrac{k}{2} + 1\right) = \dfrac{(k+1)(k+2)}{2}$.
- This is the RHS of $P(k+1)$.
Answer: By PMI, $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \in \mathbb{N}$.
In an induction proof, where exactly must the inductive hypothesis be used, and what does it mean if it is never used?
Solution- It is used inside the inductive step, at the moment you replace the "first $k$ terms / the $k$-case expression" by its assumed value.
- If the proof of $P(k+1)$ never invokes $P(k)$, you have effectively proved $P(k+1)$ directly for all $k$ — which is rarely what induction problems require.
- That signals either a non-inductive (direct) proof or, more often, a gap in the argument.
Answer: The hypothesis is the bridge from $k$ to $k+1$; an unused hypothesis means the step is not genuinely inductive.
State the full skeleton you would write to prove "$P(n): 3^n \ge 2n + 1$ for all $n \ge 1$" (you need not finish the algebra).
Solution- 1. Statement: $P(n): 3^n \ge 2n + 1$.
- 2. Base: $P(1)$: $3 \ge 3$. True.
- 3. Hypothesis: assume $3^k \ge 2k + 1$.
- 4. Step: show $3^{k+1} \ge 2(k+1) + 1$, using $3^{k+1} = 3\cdot 3^k \ge 3(2k+1)$ and then $3(2k+1) \ge 2k + 3$.
- 5. Conclude: by PMI, $P(n)$ holds for all $n \ge 1$.
Answer: The five-line skeleton — statement, base, hypothesis, step, conclusion — is the template for every induction proof.
Why does the principle of mathematical induction work — what property of $\mathbb{N}$ does it rest on?
Solution- Every natural number is reached from $1$ by adding $1$ a finite number of times.
- The base case secures the value $1$; the inductive step secures the move from any value to the next.
- Together they cover every natural number, since there is no $n$ that is not reachable by these two facts.
Answer: Induction encodes the way $\mathbb{N}$ is generated ($1$, then "$+1$ repeatedly"), which is exactly why it proves statements for all natural numbers.