Learn – Math circle – Mathematical induction

1 Exercises
- 1.1 Problem set
- 1.2 Problem set

Exercises

Problem set

Prove each of the following using mathematical induction.

$2^n > 6n$ for all $n\ge 6$ .
$n^n > n!$ for all $n \ge 2$ .
$n! > 2^n$ for all $n \ge 4$ .
$1+2+3+\cdots+n = \frac{n(n+1)}{2}$ , for all $n\in \mathbb{N}$ .
$2+4+6+\cdots+2n = n(n+1)$ , for all $n\in \mathbb{N}$ .
$1+3+5+\cdots+(2n-1) = n^2$ , for all $n\in \mathbb{N}$ .
$1+4+7+\cdots+(3n-2) = \frac{n(3n-1)}{2}$ , for all $n\in \mathbb{N}$ .
$1^2+2^2+3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}$ , for all $n \in \mathbb{N}$ .

Problem set

Prove that $7 \mid (8^n-1)$ , for all $n\in\mathbb{N}$ .
Prove that $11 \mid (12^n-1)$ , for all $n\in\mathbb{N}$ .
Prove that $19 \mid (2^{2k}5^k - 1)$ , for all $n\in\mathbb{N}$ .
Prove that $a \mid \left((a+1)^n - 1\right)$ , for all $n\in\mathbb{N}$ .
Prove that $(x-1) \mid (x^n-1)$ , for all $n\in\mathbb{N}$ .
Binomial theorem states $(x+y)^n = {n \choose 0}x^n + {n \choose 1}x^{n-1}y + {n \choose 2}x^{n-2}y^2+ \cdots + {n \choose {n-1}}xy^{n-1} + {n \choose n}y^n$ , where $n$ is a natural number. Prove the theorem.
The th term of the Fibonacci sequence is defined by and . Prove that for all ,
1. $f_n < 2^n$
2. $f_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$