0

Prove that for sufficiently large $ n $ the following inequality holds: $ \binom{5n}{4n}>12^n $. Thank you in advance.

user2566092
  • 26,142
virnoy
  • 77
  • Perhaps expressing the binomial coefficient in terms of factorials and proceeding by induction might help. Either that or you might want to use an identity (perhaps Pascal's or Vandermonde's?). – Khallil Jul 22 '15 at 15:48
  • I tried induction, i.e. $ \binom{5n+5}{4n+4}=\binom{5n}{4n}\frac{(5n+1)(5n+2)(5n+3)(5n+4)(5n+5)}{(4n+1)(4n+2)(4n+3)(4n+4)} $, but I don't even know if my expansion of binomial coefficient is correct. My main idea was toshow that for some $n$ $ \frac{(5n+1)(5n+2)(5n+3)(5n+4)(5n+5)}{(4n+1)(4n+2)(4n+3)(4n+4)} $ will be greater than $ 12^n $. But I think it's not correct at all. – virnoy Jul 22 '15 at 15:50
  • @virnoy Your expansion is correct for the induction. However try to figure out why all you need to do is prove that your complicated expression with products/ratios of $(5n + k)$ and $(4n +k)$ is greater than say, 12.5 or 13, not $12^n$ (for large enough $n$). Eventually you will dominate $12^n$ for large enough $n$ if you can prove that. – user2566092 Jul 22 '15 at 15:54
  • So all I need to do is to solve the equation $ \frac{(5n+1)(5n+2)(5n+3)(5n+4)(5n+5)}{(4n+1)(4n‌​+2)(4n+3)(4n+4)}>13 $? I'm right? I don't know if I fully understood you. – virnoy Jul 22 '15 at 15:58
  • @virnoy It's an inequality, but yes that's all you need to show. And you can replace 13 with any fixed number greater than $12$ that you want, as long as it works for all $n$ large enough. – user2566092 Jul 22 '15 at 15:59
  • @virnoy No problem. And I've left out some of the details, i.e. how to show the inequality $> 12.5$ or $> 13$ or whatever holds, and also why this is enough to show that your original ${{5n} \choose {4n}}$ term will dominate $12^n$ for large enough $n$. But hopefully that won't be too hard. – user2566092 Jul 22 '15 at 16:05

3 Answers3

3

Let $a_n=\binom{5n}{4n}=\binom{5n}{n}$. We have:

$$\frac{a_{n+1}}{a_n}=5\cdot\frac{(5n+4)\cdot\ldots\cdot(4n+5)}{(5n)\cdot\ldots\cdot(4n+1)}=5\cdot\frac{(5n+4)(5n+3)(5n+2)(5n+1)}{(4n+4)(4n+3)(4n+2)(4n+1)}$$ hence: $$\frac{a_{n+1}}{a_n}\geq 5\cdot\left(\frac{5n+1}{4n+4}\right)^4 $$ and the RHS is an increasing function with respect to $n$, whose limit when $n\to +\infty$ equals: $$ 5\cdot\left(\frac{5}{4}\right)^4 = 12+\frac{53}{256} $$ hence for any $n$ big enough ($n\geq 23$) we have $\frac{a_{n+1}}{a_n}\geq 12+\frac{1}{10}$ and that is enough to prove our claim.

Barry Cipra
  • 79,832
Jack D'Aurizio
  • 353,855
2

Thanks to Stirling's approximation, $$\binom{5n}{4n} \sim \sqrt{\frac{5}{4\pi n}} \cdot 5^n \cdot \left(\frac{5}{4}\right)^{4n}$$

Now since $5 \cdot \left(\frac{5}{4}\right)^4 \approx 12.207 \dots $ $$\frac{\binom{5n}{4n}}{12^n} \sim \sqrt{\frac{5}{4\pi n}} \cdot \left(\frac{5}{4}\right)^{ (0.207 \dots ) n} \xrightarrow[n \to \infty]{}\infty$$ and therefore, for $n$ large enough, $\frac{\binom{5n}{4n}}{12^n} >1 $.

yultan
  • 1,417
  • Hi! I think it's the most clear answer. Could you give me the general formula for such approximations? – virnoy Jul 24 '15 at 16:23
0

In an answer to this question of mine, Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$, I showed that

$\binom{kn}{n} \approx \sqrt{\dfrac{k}{2\pi n(k-1)}}\left(\dfrac{k^k} {(k-1)^{k-1}}\right)^{n}$

Putting $k=5$, since $\frac{5^5}{4^4} =\frac{3125}{256} \sim 12.207 $.

$\binom{5n}{4n} =\binom{5n}{n} \approx \sqrt{\dfrac{5}{8\pi n}}\left(\dfrac{3125} {256}\right)^{n} \approx \sqrt{\dfrac{0.1989}{n}}\left(12.207\right)^{n} $.

marty cohen
  • 107,799