Proof by Mathematical Induction

Step 1 (Base case): Show the statement is true for $n = 1$.

Step 2 (Inductive hypothesis): Assume true for $n = k$.

Step 3 (Inductive step): Prove true for $n = k + 1$ using the assumption.

Step 4 (Conclusion): "By the principle of mathematical induction, the statement is true for all $n \in \mathbb{Z}^+$."

Prove $\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$.

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

Assume true for $n=k$: $\sum_{r=1}^{k} r = \frac{k(k+1)}{2}$.

Prove for $k+1$: $\sum_{r=1}^{k+1} r = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$ ✓

• State all four steps explicitly — marks for structure.
• The conclusion statement is required.
• Common types: summation, divisibility, inequalities.