How to prove formulas by mathematical induction? Step-by-step guide

Here is a complete induction proof for both examples. **Example 1: $\sum_{i=1}^{n} i = n(n+1)/2$** **Base case $n = 1$:** $1 = 1(2)/2 = 1$ ✓ **Inductive step:** Assume $\sum_{i=1}^{k} i = k(k+1)/2$. Then: \begin{align*} \sum_{i=1}^{k+1} i &= \left(\sum_{i=1}^{k} i\ ight) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} \end{align*} Thus $P(k) \Rightarrow P(k+1)$. By induction, true for all $n \in \mathbb{N}$. **Example 2: $2^n > n^2$ for $n \geq 5$** **Base case $n = 5$:** $2^5 = 32 > 25 = 5^2$ ✓ **Inductive step:** Assume $2^k > k^2$ for $k \geq 5$. \begin{align*} 2^{k+1} &= 2 \cdot 2^k > 2k^2 \\ &= k^2 + k^2 \geq k^2 + 5k \quad (k \geq 5) \\ &> k^2 + 2k + 1 = (k+1)^2 \end{align*} **Strong induction** assumes $P(1), P(2), \ldots, P(k)$ all hold to prove $P(k+1)$. Use it when $P(k+1)$ depends on more than just $P(k)$, such as in the Fibonacci recurrence $F_{n+1} = F_n + F_{n-1}$ or the fundamental theorem of arithmetic.