Proof by Mathematical Induction

Proof by Mathematical Induction — Moosa Academy

Checking a statement for $n = 1, 2, 3$ proves nothing about $n = 1000$ . Induction closes that gap with two pieces of work: show the statement holds at the start, and show that whenever it holds at one number it must hold at the next. Together those force it to hold everywhere.

Theorem The principle of mathematical induction

To prove a statement true for every natural number

n

Step 1 — Base case. Show it is true when

n = 1

Step 2 — Hypothesis. Assume it is true at some natural number

k

Step 3 — Inductive step. Prove it must then be true at

k + 1

Knock the first domino over and guarantee each one topples its neighbour, and the whole infinite row must fall. Miss either half — the first push, or the chain — and nothing follows.

Example Proving a sum formula

Prove that $1^{3} + 2^{3} + \cdots + n^{3} = \left[\dfrac{n(n+1)}{2}\right]^{2}$ for every natural number $n$ .

Step 1 — Base case

Left side at

n = 1

1^{3} = 1

Right side at

n = 1

\left[\dfrac{1 \cdot 2}{2}\right]^{2} = 1^{2} = 1

Both sides agree — the base case holds

Step 2 — Inductive hypothesis

Assume

1^{3} + 2^{3} + \cdots + k^{3} = \left[\dfrac{k(k+1)}{2}\right]^{2}

Step 3 — Inductive step

Add

(k+1)^{3}

to both sides of the hypothesis

Left becomes

1^{3} + \cdots + k^{3} + (k+1)^{3}

Right becomes

\dfrac{k^{2}(k+1)^{2}}{4} + (k+1)^{3}

Take out

\dfrac{(k+1)^{2}}{4}

\dfrac{(k+1)^{2}}{4}\bigl[k^{2} + 4(k+1)\bigr]

The bracket factors:

k^{2} + 4k + 4 = (k+2)^{2}

So the right side is

\dfrac{(k+1)^{2}(k+2)^{2}}{4} = \left[\dfrac{(k+1)(k+2)}{2}\right]^{2}

This is the original formula with $k+1$ in place of $n$ — the step is proved

Base case and inductive step both hold, so by the principle of mathematical induction the formula is true for every natural number $n$ .

Example Proving divisibility

Prove that $8^{\,n} - 1$ is divisible by $7$ for every natural number $n$ .

Step 1 — Base case

n = 1

8^{1} - 1 = 7

, which is divisible by

7

Step 2 — Inductive hypothesis

Assume

8^{\,k} - 1 = 7r

for some natural number

r

Rearranged:

8^{\,k} = 7r + 1

Step 3 — Inductive step

Multiply the hypothesis by

8

8^{\,k+1} = 8(7r + 1) = 56r + 8

Subtract

1

8^{\,k+1} - 1 = 56r + 7

Take out

7

8^{\,k+1} - 1 = 7(8r + 1)

Since $8r + 1$ is a natural number, the result is divisible by $7$

The pattern is the same as before. Start from the assumed case, do the smallest algebraic move that reaches $k+1$ , and finish by exhibiting the required factor.

Example Disproving with a counterexample

Is $2^{\,n} + 2n^{2}$ divisible by $4$ for every natural number $n$ ?

$n$	$2^{\,n} + 2n^{2}$	Divisible by 4?
1	$2 + 2 = 4$	Yes
2	$4 + 8 = 12$	Yes
3	$8 + 18 = 26$	No

$n = 3$ is a counterexample, so the statement is false. Two successes proved nothing; one failure settles the matter completely. Disproving a universal claim needs a single case, while proving one needs induction.

Note Both halves are required

A proof with only the inductive step shows that if the statement ever holds it keeps holding — but perhaps it never holds at all. A proof with only a base case checks one number and says nothing about the rest. Neither half is a proof on its own.

Summary

Induction proves a statement for all natural numbers in three steps.
Step 1: verify the base case, usually $n = 1$ .
Step 2: assume the statement is true at $n = k$ .
Step 3: use that assumption to prove it at $n = k+1$ .
For a sum, add the next term to both sides of the hypothesis and factor.
For divisibility, manipulate the hypothesis until the required factor appears.
To disprove a statement, one counterexample is enough — no induction needed.