Proving by induction: $ \frac{1\cdot3\cdot5\cdot \ldots \cdot (2n-1)}{1\cdot2\cdot3\cdot\ldots\cdot n} \leq 2^n $

Question

WTS $ \frac{1\cdot3\cdot5\cdot \ldots \cdot (2n-1)}{1\cdot2\cdot3\cdot\ldots\cdot n} \leq 2^n $ for all natural $n$.

Have checked $P_1$, and assumed $P_k$.

Trying the following argument:

$P_{k+1} = \frac{1\cdot3\cdot5\cdot \ldots \cdot (2k-1)\cdot(2k+1)}{1\cdot2\cdot3\cdot\ldots\cdot k \cdot (k+1)} = \frac{1\cdot3\cdot5\cdot \ldots \cdot (2k-1)}{1\cdot2\cdot3\cdot\ldots\cdot k}\cdot \frac{2k+1}{k+1} \leq 2^k \cdot\frac{2k+1}{k+1} \leq 2^{k+1}\cdot \frac{2k+1}{k+1}$ using $P_k$ and that these are all positive numbers.

Now dividing through by $\frac{2k+1}{k+1}$ would give the desired result.

I just feel like I've done something wrong here. Can anyone tell me if I've overlooked anything?

Answer 1

You've basically got the right idea, except your last inequality is too weak (and not at all needed - you've basically just added an extra factor of $2$ without need). You've shown that

$$P_{k + 1} = P_k \cdot \frac{2k + 1}{k + 1}$$

Now we have that $P_k \le 2^k$ by hypothesis, and it's easy to see that

$$\frac{2k + 1}{k + 1} \le 2$$

for every $k \ge 0$. This implies $P_{k + 1} \le 2^k \cdot 2$, which is what you want.

Answer 2

All you need is to prove that: $\dfrac{2k+1}{k+1} \leq 2$

Answer 3

Here is an alternate solution that gives a bit more insight.

$\frac{1 \cdot 3 \cdots (2n-1)}{n!} = \frac{(2n)!}{2^n(n!)^2}$ so we have to prove $2^{2n} \ge \frac{(2n)!}{(n!)^2} = \dbinom{2n}{n}$.

However, $2^{2n} = \sum_{k = 0}^{2n} \dbinom{2n}k > \dbinom{2n}n$ and the conclusion follows. Obviously, the inequality is very weak.