0
$\begingroup$

Show that $\binom{2n}{n} < 2^{2n - 2}$ for all $n \geq 5$.

Can I get some help please? I started by trying to prove this by induction, For the base case $n=5$, I showed the inequality is true. For the the induction step, I assumed that the inequality is true and started trying to show it's true for $n+1$. So $\binom{2n+2}{n+1}$ and I broke it down by combinatorics to get $2\binom{2n}{n}+\binom{2n}{n+1}+\binom{2n}{n-1}$ which is less than $2\cdot 2^{2n-2}+\binom{2n}{n+1}+\binom{2n}{n-1}$ using the inductive step and I don't know how to continue.

$\endgroup$
2
  • $\begingroup$ Use factorial formula for ${2n+2 \choose n+1}$ and ${2n \choose n}$, then use $\frac{(2n+1)(2n+2)}{(n+1)(n+1)} < 4$. Ratio $\dfrac{2n+2 \choose n+1}{2n \choose n}=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}$ also can be shown using combinatorics. $\endgroup$ Apr 15, 2022 at 10:54
  • $\begingroup$ Please type your question rather than posting an image since images cannot be searched. $\endgroup$ Apr 15, 2022 at 11:50

2 Answers 2

1
$\begingroup$

Base Case: $n = 5$ can be checked manually.

Now, we need to show that $$\binom{2n + 2}{n + 1} < 2 ^ {2n}$$ assuming that $$\binom{2n}{n} < 2 ^ {2n - 2}$$

Note that it suffices to show that $$\frac{\binom{2n + 2}{n + 1}}{\binom{2n}{n}} < 4 \text{ (Why?)}$$

Expanding and cross-multiplying (all terms are positive), we get $$\frac{(2n + 1)(2n + 2)}{(n + 1)(n + 1)} < 4$$ $$\iff \frac{2n + 1}{n + 1} < 2$$ which is true.

$\endgroup$
1
$\begingroup$

Proof:

When $n=5$, we have $252=\left( \begin{array}{c}10\\5\\\end{array} \right) \le 4^4=256$.

Then $\forall n\ge 5$, suppose that $\left( \begin{array}{c}2n\\n\\\end{array} \right) < 4^{n-1}$ is true, and we have:

\begin{align} &1<2\\ \Rightarrow ~~&2n+1<2n+2\\ \Rightarrow ~~&\frac{2n+1}{n+1}<2\\ \Rightarrow ~~&\frac{\left( 2n+1 \right) \left( 2n+2 \right)}{\left( n+1 \right) \left( n+1 \right)}<4\\ \Rightarrow ~~&\frac{\left( 2n+1 \right) \left( 2n+2 \right)}{\left( n+1 \right) \left( n+1 \right)}\times \left( \begin{array}{c} 2n\\ n\\ \end{array} \right) <4^n\\ \Rightarrow ~~&\frac{\left[ 2\left( n+1 \right) \right] !}{\left( n+1 \right) !\left( n+1 \right) !}<2^{2\left( n+1 \right) -2}, \end{align}

i.e., the original statement is also true for $(n+1)$.

So $\left( \begin{array}{c}2n\\n\\\end{array} \right) < 2^{2n-2}$ holds for all $n\ge 5$.


P.S.

I see that @Ivan Kaznacheyeu has given the tip, so this answer is just an implementation of it.

$\endgroup$

You must log in to answer this question.