Mathematical Induction is used to prove that the statement of the problem $P(n)$ is true for all natural numbers $n$. Mathematical Induction consists of proving the following three theorems.
Theorem 1 (Base of Induction): The statement of the problem is true for $n = 1$.
Theorem 2 (Inductive Step): If the statement is true for some $n = k$, then it must also be true for $n = k + 1$.
Theorem 3 (Peano Axiom): If Theorems 1 and 2 hold, then the statement of the problem is true for all natural numbers $n$.
Problem (42 Points Training, 2019)
Show that for all $n \in \mathbb{N}$
$$ 1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1) \leq n^n $$
Solution
Theorem 1 (Base of Induction): The inequality is true for $n = 1$: $1 \leq 1^1$.
Theorem 2 (Inductive Step): Let us assume that the inequality holds for $n = k$, i.e.
$$ 1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1) \leq n^n $$
Train for Math Olympiads
Learn more
Therefore by the inductive hypothesis
$$ 1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1) \cdot (2k+1) \leq k^k \cdot (2k+1) < (k+1)^{k+1} $$
The last inequality comes from the Bernoulli’s Inequality
$$ \frac{(k+1)^{k+1}}{k^k} = \left( \frac{k+1}{k} \right)^{k} (k+1) = \left( 1+ \frac{1}{k} \right)^{k} (k+1) \geq 2 (k+1) \geq 2k+1$$
and therefore the inequality holds for $n=k+1$.
Theorem 3 (Peano Axiom): Since Theorems 1 and 2 hold, then the inequality is true for all $n \in \mathbb{N}$.
