Mathematical Induction Reference

Mathematical Induction

Induction proves a statement for every integer in a starting range by checking one first case and showing each case leads to the next.

Solved Examples

Jump directly to a worked example by type.

Prove a Sum Formula
Prove Divisibility
Strong Induction: Prime Factors

Fact Table

Idea	Meaning	Use or Check
Base case	Verify the first value in the claimed range.	Use the exact starting index.
Inductive hypothesis	Assume the statement holds at an arbitrary index $k$.	The hypothesis is temporary and specific.
Inductive step	Use the hypothesis to prove the statement at $k+1$.	This connects consecutive cases.
Strong induction	Assume all earlier cases through $k$ to prove case $k+1$.	Useful when the next case depends on more than one earlier case.

Content Formulas

Induction Pattern

$$P(n_0),\quad P(k)\Rightarrow P(k+1)\quad\Longrightarrow\quad P(n)\text{ for all }n\ge n_0$$

First $n$ Integers

$$1+2+\cdots+n=\frac{n(n+1)}2$$

The inductive step is not a test of a few values. It must begin with an arbitrary $k$ and prove the implication from case $k$ to case $k+1$.

Classic Examples

Prove a Sum Formula

Prove by induction that $1+2+\cdots+n=n(n+1)/2$ for every integer $n\ge1$.

Solution Steps

Check $n=1$.
Assume the formula holds for $n=k$.
Add the next term $k+1$ and simplify to the formula for $k+1$.

$$n=1:\quad 1=\frac{1(2)}2$$ $$1+\cdots+k=\frac{k(k+1)}2$$ $$1+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1)$$ $$=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}2$$

Prove Divisibility

Prove that $6$ divides $7^n-1$ for every integer $n\ge1$.

Solution Steps

Check the base case $n=1$.
Assume $7^k-1$ is divisible by $6$.
Rewrite the next expression to use the inductive hypothesis.

$$7^1-1=6$$ $$7^{k+1}-1=7(7^k-1)+6$$ The first term is divisible by 6 by the hypothesis, and the second is divisible by 6.

Strong Induction: Prime Factors

Show that every integer $n\ge2$ is prime or can be written as a product of primes.

Solution Steps

For a composite $n$, write $n=ab$ with $2\le a,b\lt n$.
Assume each smaller integer at least 2 is prime or a product of primes.
Apply the hypothesis to both factors.

Base case: $2$ is prime. If $n$ is prime, the statement holds. If $n=ab$ is composite, then $a$ and $b$ are smaller integers at least 2. By strong induction, each factor is prime or a product of primes; multiplying their factorizations gives one for $n$.