Exercise 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 positive integers $n$.

A complete proof by Mathematical Induction consists of three parts:

If all three parts are established, we conclude $P(n)$ is true for all $n\in \mathbb{N}$.

---

Standard Proof Template

To prove: $P(n)$ for all $n\ge 1$.

Step 1 — Base Case: Show $P(1)$ is true by direct substitution.

Step 2 — Inductive Hypothesis: Assume $P(k)$ is true, i.e., assume the statement holds when $n=k$.

Step 3 — Inductive Step: Prove $P(k+1)$ is true using the assumption from Step 2.

Conclusion: By the Principle of Mathematical Induction, $P(n)$ is true for all $n\in \mathbb{N}$.

---

Worked Example 1 — Summation Formula

Prove: $1+2+3+\cdots +n=\frac{n(n+1)}{2}$ for all $n\in \mathbb{N}$.

Base Case ($n=1$): $\text{LHS}=1,\text{RHS}=\frac{1\cdot 2}{2}=1✓$

Inductive Hypothesis: Assume the formula holds for $n=k$: $1+2+\cdots +k=\frac{k(k+1)}{2}$

Inductive Step: Prove for $n=k+1$: $1+2+\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}$

This is exactly the formula with $n=k+1$. $✓$

Conclusion: The formula holds for all $n\in \mathbb{N}$.

---

Worked Example 2 — Divisibility

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

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

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

Inductive Step: Consider $5^{k+1}-1$: $5^{k+1}-1=5\cdot 5^k-1=5(5^k-1)+5-1=5(4m)+4=4(5m+1)$

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

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

---