Principle of Mathematical Induction

Introduction. The earliest implicit use of a proof by induction is credited to Al-Karaji, around 100 AD; the first explicit statement of the principle as a method is credited to Pascal, in 1665. Mathematical induction is a powerful and easy-to-use method for proving that a statement $P(n)$, framed for every positive integer $n$, is true for all $n \in N$ at once — without checking each $n$ individually, which is impossible since there are infinitely many of them.

The four steps of the Principle of Mathematical Induction. To prove a statement $P(n)$ for all $n \in N$:

• Step 1 (Foundation). Prove that $P(n)$ is true for $n=1$. (It is good practice, though not compulsory, to also check $P(2)$ and $P(3)$ when $P(1)$ is a trivial check — this builds confidence and insight into the pattern before the general step.)
• Step 2 (Assumption). Assume that $P(n)$ is true for $n=k$, for some particular natural number $k$. This assumed statement is called the induction hypothesis.
• Step 3 (Succession). Using Step 2 as a known fact, prove that $P(n)$ is then also true for $n=k+1$.
• Step 4 (Induction). Conclude, by the Principle of Mathematical Induction, that $P(n)$ is true for every $n \in N$.

Why this works — the domino picture. A row of dominoes standing close enough together that a falling domino knocks over the next one gives a physical feel for why these four steps are enough (Fig. 4.1). Step 1 is the first domino actually falling. Steps 2 and 3 together say: if the $k$th domino falls, then the $(k+1)$th domino also falls — a conditional fact about the row, true regardless of which particular domino you pick as the $k$th. Step 4 then says that because the first domino falls, and every domino's fall drags down the next one, the whole infinite row must fall, one after another, with no gap: 1st falls, so 2nd falls, so 3rd falls, and so on forever. The logical proof of $P(n)$ works exactly the same way — Step 1 starts the chain and the conditional fact proved in Step 3 keeps propagating it forward through every natural number.

Stepwise explanation, formally restated. Formulate the theorem as a statement $P(n)$ about a positive integer $n$. (I) Verify $P(1)$ directly (and, for insight, $P(2)$, $P(3)$ if helpful). (II) Assume $P(k)$ true for a positive integer $k$. (III) Prove $P(k+1)$ using the assumption in (II). (IV) Invoke the Principle of Mathematical Induction to conclude $P(n)$ holds for every positive integer $n$.

Illustration — sum of the first $n$ positive integers. Let $P(n): 1+2+3+\cdots+n = \dfrac{n(n+1)}{2}$.

Step 1 (Foundation). For $n=1$: L.H.S. $=1$, R.H.S. $=\dfrac{1(1+1)}{2}=1$; trivially true. As a sanity check, $1+2=\dfrac{2(2+1)}{2}=3$ and $1+2+3=\dfrac{3(3+1)}{2}=6$, so $P(2)$ and $P(3)$ hold as well.

Step 2 (Assumption). Assume $P(n)$ true for $n=k$: $1+2+3+\cdots+k=\dfrac{k(k+1)}{2}$.

Step 3 (Succession). We must show $1+2+3+\cdots+k+(k+1)=\dfrac{(k+1)(k+2)}{2}$. Starting from the L.H.S. and using Step 2 to replace the sum up to $k$: L.H.S. $=\dfrac{k(k+1)}{2}+(k+1)=(k+1)\left(\dfrac{k}{2}+1\right)=(k+1)\cdot\dfrac{k+2}{2}=\dfrac{(k+1)(k+2)}{2}=$ R.H.S. So $P(k+1)$ is proved true, given $P(k)$.

Step 4 (Induction). By the Principle of Mathematical Induction, $P(n)$ is true for every positive integer $n$.

Solved Example 1. Prove by induction that $1.3+2.5+3.7+\cdots+n(2n+1)=\dfrac{n}{6}(n+1)(4n+5)$ for all $n\in N$.

Solution. Let $P(n)$ be this statement. Step (I). For $n=1$: L.H.S. $=1.3=3$; R.H.S. $=\dfrac{1}{6}(2)(9)=3$. Equal, so $P(1)$ holds. Step (II). Assume $P(k)$: $1.3+2.5+\cdots+k(2k+1)=\dfrac{k}{6}(k+1)(4k+5)$. Step (III). We must show $1.3+2.5+\cdots+(k+1)(2k+3)=\dfrac{k+1}{6}(k+2)(4k+9)$. Starting from L.H.S. $=\dfrac{k}{6}(k+1)(4k+5)+(k+1)(2k+3)$ (using Step II) $=(k+1)\left[\dfrac{k(4k+5)}{6}+(2k+3)\right]=(k+1)\cdot\dfrac{4k^2+5k+12k+18}{6}=(k+1)\cdot\dfrac{4k^2+17k+18}{6}=\dfrac{(k+1)(k+2)(4k+9)}{6}=$ R.H.S. So $P(k+1)$ holds. Step (IV). By induction $P(n)$ is true for all $n\in N$.

Solved Example 2. Prove $a+ax+ax^2+\cdots+ax^{n-1}=\sum_{r=1}^{n}ax^{r-1}=a\dfrac{1-x^n}{1-x}$, for all $n\in N$, $x\neq 1$ (the geometric-series sum formula).

Solution. Step (I). For $n=1$: L.H.S. $=a$; R.H.S. $=a\dfrac{1-x}{1-x}=a$. Equal, so true. Step (II). Assume $P(k)$: $a+ax+\cdots+ax^{k-1}=a\dfrac{1-x^k}{1-x}$. Step (III). Show $a+ax+\cdots+ax^{k-1}+ax^k=a\dfrac{1-x^{k+1}}{1-x}$. L.H.S. $=a\dfrac{1-x^k}{1-x}+ax^k$ (by Step II) $=a\cdot\dfrac{(1-x^k)+x^k(1-x)}{1-x}=a\cdot\dfrac{1-x^k+x^k-x^{k+1}}{1-x}=a\dfrac{1-x^{k+1}}{1-x}=$ R.H.S. Step (IV). True for all $n\in N$, $x\neq 1$, by induction.

Solved Example 3. Prove $5^{2n}-1$ is divisible by $6$, for all $n\in N$. Solution. Let $P(n)$ be: $5^{2n}-1=6m$ for some $m\in N$. Step (I). $n=1$: $5^2-1=24=6\cdot4$, so divisible by 6; $P(1)$ true. Step (II). Assume $5^{2k}-1=6a$, so $5^{2k}=6a+1$. Step (III). $5^{2(k+1)}-1=5^{2k}\cdot5^2-1=(6a+1)(25)-1=150a+25-1=150a+24=6(25a+4)$, a multiple of 6; $P(k+1)$ true. Step (IV). True for all $n\in N$ by induction.

Solved Example 4. Prove $n!\ge2^n$ for all $n\in N$, $n\ge4$. Solution. Step (I). At $n=4$: L.H.S. $=4!=24$, R.H.S. $=2^4=16$; since $24\ge16$, true at $n=4$ (note the statement genuinely fails for $n=1,2,3$, which is why the claim is restricted to $n\ge4$ from the start). Step (II). Assume $k!\ge2^k$ for some $k\ge4$. Step (III). Since $k\ge4$, also $k+1\ge5\ge2$, so $(k+1)!=(k+1)\,k!\ge2\cdot2^k=2^{k+1}$ using Step II; true for $k+1$. Step (IV). By induction, $n!\ge2^n$ for all $n\ge4$.

Solved Example 5. Given the recurrence $t_{n+1}=3t_n+4$, $t_1=1$, prove $t_n=3^n-2$. Solution. Step I. $n=1$: R.H.S. $=3-2=1=$ L.H.S. (the given $t_1$); also $t_2=3t_1+4=7$ matches R.H.S. $3^2-2=7$. Step II. Assume $t_k=3^k-2$. Step III. $t_{k+1}=3t_k+4=3(3^k-2)+4=3^{k+1}-6+4=3^{k+1}-2$, matching the claimed formula at $k+1$. Step IV. By induction, $t_n=3^n-2$ for all $n\in N$, given that recurrence.

Solved Example 6. Prove $2^n>n$ for all $n\in N$. Solution. Step (I). $n=1$: $2^1=2>1$; true. Step (II). Assume $2^k>k$. Step (III). $2^{k+1}=2\cdot2^k>2k$ (using Step II) $=k+k\ge k+1$ (since $k\ge1$); so $2^{k+1}>k+1$. Step (IV). True for all $n\in N$ by induction.

Remarks — both conditions are needed, illustrated by a deliberately false example. In an induction proof, both (i) $P(1)$ true and (ii) 'if $P(k)$ true then $P(k+1)$ true' must hold. If only the second condition holds but the first fails, the conclusion can be false for every $n$, even though the succession step works perfectly. The textbook demonstrates this with $P(n): 1.6+2.9+3.12+\cdots+n(3n+3)=n^3+3n^2+2n+3$. Assuming $P(k)$ true and checking $P(k+1)$: L.H.S. $=k^3+3k^2+2k+3+(k+1)(3k+6)$ (by the assumption) $=k^3+3k^2+2k+3+3k^2+9k+6=k^3+6k^2+11k+9$, which regroups exactly as $(k+1)^3+3(k+1)^2+2(k+1)+3$ — so the succession step genuinely holds, and 'if $P(k)$ then $P(k+1)$' is true. But checking Step I directly: at $n=1$, L.H.S. $=1.6=6$ while R.H.S. $=1+3+2+3=9$; these are unequal, so $P(1)$ is actually false. Hence $P(n)$ is false for every $n \in N$ despite the succession step working — a warning that Step 1 can never be skipped or assumed.