2

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?

Alec
  • 4,094

3 Answers3

4

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

DeepSea
  • 77,651
  • So you also think the last inequality is too weak? Is there a fixed rule to follow here? I considered it given because of the added factor of 2. – Alec Jun 06 '14 at 05:50
4

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.

Sandeep Silwal
  • 8,135
3

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.

  • Ok, that's very doable. But why was the last inequality too weak? – Alec Jun 06 '14 at 05:29
  • @Aleksander You had an unnecessary multiplication by $2$ - if you had gone through with proving that $(2k + 1) / (k + 1) < 2$, it would have followed that $P_{k + 1} \le 2^k \cdot 4$. –  Jun 06 '14 at 06:09