Mathematical Induction — Exercises

Contents

1$\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$ easy

Prove by induction for $n \geq 1$.

2$\displaystyle\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$ easy

Prove by induction.

3$\displaystyle\sum_{i=1}^{n} i^3 = \Bigl(\dfrac{n(n+1)}{2}\Bigr)^2$ medium

Prove by induction and verify with SymPy.

4$\displaystyle\sum_{i=1}^{n} (2i - 1) = n^2$ easy

Prove by induction.

5Geometric sum: $\displaystyle\sum_{i=0}^{n} r^i = \dfrac{r^{n+1} - 1}{r - 1}$ for $r \neq 1$ medium

Prove by induction on $n$.

6$2^n > n^2$ for $n \geq 5$ medium

Be careful with the starting index. Verify $n = 4$ does not work.

7$n < 2^n$ for $n \geq 1$ easy

Prove by induction.

8A set of $n$ elements has $2^n$ subsets medium

Prove by induction on $n$.

9$3 \mid n^3 - n$ for every $n \in \mathbb{N}$ medium

Prove by induction on $n \geq 0$.

10$\displaystyle\sum_{i=1}^{n} \dfrac{1}{i^2} \leq 2 - \dfrac{1}{n}$ for $n \geq 1$ hard

Stronger than $\sum 1/i^2 < 2$ — the extra $-1/n$ is the trick that makes induction work.

11Strong induction — stamps of 4 and 5 cents hard

Prove that every postage value $n \geq 12$ cents can be made with stamps of 4¢ and 5¢ only. Verify with Python by brute force.

12Strong induction — $F_n \leq 2^n$ hard

The Fibonacci sequence is $F_0 = 0,\, F_1 = 1,\, F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Prove by strong induction that $F_n \leq 2^n$ for every $n \geq 0$.

Going further

• Prove $\sum_{i=1}^{n} i \cdot i! = (n+1)! - 1$ by induction.
• Prove $n! > 2^n$ for $n \geq 4$ (the lesson did the strict version).
• Prove by strong induction: every integer $n \geq 2$ has a prime factorisation.
• Spot the bug in the "all horses are the same colour" proof — which step fails?

Open the main lesson for the matching theory.