Inequality Induction

Induction is an untouched topic in this blog so far, but I finally found a good question about it. It's not hard, but it's rather challenging.

Prove by induction:
(1 * 3 * 5 * 7 * ... * (2n - 1)) / (1 * 2 * 3 * 4 * ... * n) < 2ⁿ/√(2n + 1)

The first step in proving an induction is checking whether it works at all. Let's plug 1 for n:
1 / 1 < 2¹/√(2 + 1)
1 / 1 < 2 / √3 - correct!

Assume that the inequality is correct for n = k (k is natural)
(1 * 3 * 5 * ... * (2k - 1)) / (1 * 2 * 3 * ... * k) < 2^k/√(2k + 1)

Now let's prove that if the inequality is right for n = k, it is right for n = k + 1:
(1 * 3 * 5 * ... * (2k - 1) * (2k + 1)) / (1 * 2 * 3 * ... * k * (k + 1)) < 2^{k + 1}/√(2k + 3)

First, we know that (1 * 3 * 5 * ... * (2k - 1)) / (1 * 2 * 3 * ... * k) is smaller than 2^k/√(2k + 1), so it's definitely smaller than 2^{k + 1}/√(2k + 3). For this reason, we can place 2^k/√(2k + 1) instead of this big expression:
(2^k * (2k + 1))/(k + 1)√(2k + 1) < 2^{k + 1}/√(2k + 3)

Divide by 2^k:
(2k + 1)/(k + 1)√(2k + 1) < 2 / √(2k + 3)

Square both sides and cross multiply (k is natural, all positive):
4k² + 8k + 3 < 4k² + 8k + 3
3 < 4 - always true

We have shown that if n = k is correct, n = k + 1 is also correct. By checking that n = 1 is correct, we have proven that the inequality is correct for all natural numbers.

Enjoy,
Nadav

nadavs