12
$\begingroup$

I would like to prove the following inequality, for $n=0,1,2,...$, $$ \binom{2n}{n}\leq 4^n.$$ I already proved it by induction, and I'm looking for another proof.

$\endgroup$
11
$\begingroup$

$\displaystyle 4^n=(1+1)^{2n} =\sum_{k=0}^{2n}\binom{2n}{k}\geq\binom{2n}{n}$

$\endgroup$
13
$\begingroup$

A bit more can be proven with a bit more work. For $k\ge0$, we have the inequality $$ \begin{align} \left(\frac{k+\frac12}{k+1}\right)^2 &=\frac{k^2+k+\frac14}{k^2+2k+1}\\ &\le\frac{k+1}{k+2}\tag{1} \end{align} $$ because cross-multiplication gives $k^3+3k^2+\frac94k+\frac12\le k^3+3k^2+3k+1$.

Using $(1)$ yields $$ \begin{align} \frac{\binom{2k+2}{k+1}}{\binom{2k}{k}} &=4\frac{k+\frac12}{k+1}\\ &\le4\sqrt{\frac{k+1}{k+2}}\tag{2} \end{align} $$ Multiplying $(2)$ for $k=0$ to $k=n-1$, we get $$ \boxed{\bbox[5px]{\displaystyle\binom{2n}{n}\le\frac{4^n}{\sqrt{n+1}}}}\tag{3} $$


As Olivier Oloa comments, Stirling's Formula tells us that $$ \lim_{n\to\infty}\binom{2n}{n}\frac{\sqrt{\pi n}}{4^n}=1\tag{4} $$ In fact, using inequalities similar to $(2)$, in this answer, it is shown that $$ \boxed{\bbox[5pt]{\displaystyle\frac{4^n}{\sqrt{\pi(n+\frac13)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi(n+\frac14)}}}}\tag{5}$$

$\endgroup$
  • $\begingroup$ Nice inequality, especially knowing that the true order is $$ \binom{2n}{n}\sim \frac{4^n}{\sqrt{\pi}\sqrt{n}}. $$(+1) $\endgroup$ – Olivier Oloa Sep 14 '14 at 21:37
  • $\begingroup$ @OlivierOloa: We actually have that $$\binom{2n}{n}\frac{\sqrt{\pi n}}{4^n}\nearrow1$$ which means that $\frac{4^n}{\sqrt{\pi n}}$ is an overestimate as well as an asymptotic approximation. Come to think of it, I can prove this using a similar argument and Stirling's Formula. Time for an edit :-) $\endgroup$ – robjohn Sep 14 '14 at 23:24
6
$\begingroup$

Let $n \in \mathbb{N}.$ You may write

$$ 4^n=2^{2n} =(1+1)^{2n}= \sum_{k=0}^{2n}\binom{2n}{k}\geq\binom{2n}{n}. $$

$\endgroup$
1
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{{2n \choose n}\leq 4^{n}:\ {\large ?}}$

\begin{align} \binom{2n}{n}&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \end{align}

\begin{align} \color{#66f}{\large\verts{\binom{2n}{n}}}&= \verts{\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}} \,{\dd z \over 2\pi\ic}}\leq \oint_{\verts{z}\ =\ 1}\verts{\pars{1 + z}^{2n}} \,{\verts{\dd z} \over 2\pi}<\pars{1 + 1}^{2n}=\color{#66f}{\LARGE 4^{n}} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.