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 $19 \mid (2^{2k}5^k - 1)$ , for all $n\in\mathbb{N}$ .
Prove that $(x-1) \mid (x^n-1)$ , for all $n\in\mathbb{N}$ .
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]$