Mathematical Induction

Proof by Induction

Mathematical induction proves statements of the form $P(n)$ for all $n \geq n_0$:

1. Base case: Prove $P(n_0)$.
2. Inductive step: Assume $P(k)$ (inductive hypothesis), prove $P(k+1)$.

Classic Example: Sum Formula

Theorem: $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

Proof: Base case $n=1$: $1 = 1 \cdot 2 / 2$ ✓. Inductive step: assume it holds for $k$. Then: $\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2} \checkmark$

Sum of Squares

$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

Strong Induction

In strong induction, the hypothesis is $P(1) \land P(2) \land \cdots \land P(k)$, not just $P(k)$. This is equivalent in power but more convenient for some proofs (e.g., unique prime factorization).

def verify_sum_of_squares(n):
    actual = sum(i**2 for i in range(1, n+1))
    formula = n * (n + 1) * (2 * n + 1) // 6
    return actual == formula

print(verify_sum_of_squares(100))  # True

Your Task

Implement the three verification functions below.