7.1 Principle of Mathematical Induction

What is Mathematical Induction?

The Principle of Mathematical Induction (PMI) is a proof technique used to establish that a statement $P(n)$ is true for all natural numbers $n$ (or for all integers $n\ge n_0$).

It is conceptually similar to a chain of falling dominoes: if the first domino falls, and each domino knocks down the next one, then all dominoes will eventually fall.

---

Structure of an Induction Proof

A complete proof by induction has three parts:

1. Basis Step (Base Case)

Prove that $P(n_0)$ is true, where $n_0$ is the smallest value in the domain (usually $n_0=1$, but sometimes $n_0=2,3,4,\dots$ depending on the statement).

2. Inductive Hypothesis

Assume that $P(k)$ is true for some arbitrary natural number $k\ge n_0$. This assumption is called the Inductive Hypothesis.

3. Inductive Step

Using the inductive hypothesis, prove that $P(k+1)$ is also true. That is, show: $P(k)⟹P(k+1)$

Once both steps are complete, by the Principle of Mathematical Induction, $P(n)$ is true for all $n\ge n_0$.

---

Types of Statements Proved by Induction

A. Summation Formulae

To prove $\sum _{i=1}^n{a}_i=S_n$:

• Basis: Verify $S_1$ (or $S_{n_0}$) is true.
• Inductive Step: Assume $\sum _{i=1}^k{a}_i=S_k$. Add $a_{k+1}$ to both sides and show the result equals $S_{k+1}$.

Example: Prove $1+2+3+\cdots +n=\frac{n(n+1)}{2}$

Basis ($n=1$): LHS $=1$, RHS $=\frac{1\cdot 2}{2}=1$. ✓

Inductive Hypothesis: Assume $1+2+\cdots +k=\frac{k(k+1)}{2}$.

Inductive Step: Show it holds for $n=k+1$: $1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}$ This is exactly $S_{k+1}$. ✓

---

B. Product Series

To prove $\prod _{i=2}^{n}f(i)=P_n$:

• Inductive Step: Multiply both sides of the inductive hypothesis by the $(k+1{)}^{\text{th}}$ factor $f(k+1)$, then simplify to obtain $P_{k+1}$.

---

C. Divisibility Statements

To prove that an expression $f(n)$ is divisible by some integer $d$:

• Basis: Show $d\mid f(n_0)$.
• Inductive Step: Assume $d\mid f(k)$. Write $f(k+1)$ in terms of $f(k)$ and show $d\mid f(k+1)$.

Example: Prove $5^n-1$ is divisible by $4$ for all $n\in \mathbb{N}$.

Basis ($n=1$): $5^1-1=4$, which is divisible by $4$. ✓

Inductive Hypothesis: Assume $4\mid (5^k-1)$, i.e., $5^k-1=4m$ for some integer $m$.

Inductive Step: $5^{k+1}-1=5\cdot 5^k-1=5(5^k-1)+4=5(4m)+4=4(5m+1)$ Since $5m+1$ is an integer, $4\mid (5^{k+1}-1)$. ✓

---

D. Inequalities

To prove $f(n)>g(n)$ or $f(n)\ge g(n)$:

• Use the inductive hypothesis to bound or estimate $f(k+1)$ in terms of $f(k)$.

---

Key Algebraic Technique

In the inductive step for summation proofs, the key move is: $S_{k+1}=S_k+a_{k+1}$ Substitute the inductive hypothesis for $S_k$, then factor or simplify to match the formula with $n$ replaced by $k+1$.

---

Summary Table