Exercise 7.1 — Question 2

Mathematical Induction: Proving Summation Formulae

This exercise applies the Principle of Mathematical Induction (PMI) to prove summation identities. Every proof must follow the three-step structure:

1. Base Case (Step 1): Verify the statement is true for $n=1$.
2. Inductive Hypothesis (Step 2): Assume the statement is true for $n=k$.
3. Inductive Step (Step 3): Prove the statement is true for $n=k+1$ using the hypothesis.
4. Conclusion: Since the base case holds and the inductive step is valid, the statement is true for all $n\in \mathbb{N}$.

---

Worked Examples

Part (i): Prove that $1+3+5+\cdots +(2n-1)=n^2$

Step 1 — Base Case ($n=1$): $\text{LHS}=1,\text{RHS}=1^2=1$ LHS = RHS ✓

Step 2 — Inductive Hypothesis: Assume true for $n=k$: $1+3+5+\cdots +(2k-1)=k^2$

Step 3 — Inductive Step ($n=k+1$): We must show: $1+3+\cdots +(2k-1)+(2(k+1)-1)=(k+1{)}^2$

Starting from the hypothesis: $k^2+(2k+1)=k^2+2k+1=(k+1{)}^2✓$

Conclusion: By PMI, $1+3+5+\cdots +(2n-1)=n^2$ for all $n\in \mathbb{N}$.

---

Part (ii): Prove that ${\sum }_{r=1}^{n}r=\frac{n(n+1)}{2}$

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

Step 2 — Inductive Hypothesis: Assume true for $n=k$: $1+2+3+\cdots +k=\frac{k(k+1)}{2}$

Step 3 — Inductive Step ($n=k+1$): We must show: $1+2+\cdots +k+(k+1)=\frac{(k+1)(k+2)}{2}$

$\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}✓$

Conclusion: By PMI, ${\sum }_{r=1}^{n}r=\frac{n(n+1)}{2}$ for all $n\in \mathbb{N}$.

---

Part (iii): Prove that ${\sum }_{r=1}^n{r}^2=\frac{n(n+1)(2n+1)}{6}$

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

Step 2 — Inductive Hypothesis: Assume true for $n=k$: $1^2+2^2+\cdots +k^2=\frac{k(k+1)(2k+1)}{6}$

Step 3 — Inductive Step ($n=k+1$): We must show: $\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2=\frac{(k+1)(k+2)(2k+3)}{6}$

$\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2=\frac{k(k+1)(2k+1)+6(k+1{)}^2}{6}$ $=\frac{(k+1)[k(2k+1)+6(k+1)]}{6}=\frac{(k+1)(2k^2+7k+6)}{6}$ $=\frac{(k+1)(k+2)(2k+3)}{6}✓$

Conclusion: By PMI, ${\sum }_{r=1}^n{r}^2=\frac{n(n+1)(2n+1)}{6}$ for all $n\in \mathbb{N}$.

---

Key Terminology