4
$\begingroup$

I reduced a homework problem in combinatorics to giving an asymptotic estimate for $\sum_{k=0}^n{n \choose k}^3$.

I assume Stirling's approximation can help, but I'm not experienced with making estimates and need some help.

  • 0
    Just for fun, Mathematica spits out $\, _3F_2(-n,-n,-n;1,1;-1)$, the generalized Hypergeometric function.2012-04-21

2 Answers 2

3

Well, there is never just a single asymptotic estimate for a quantity, and how tight you want to the estimate to be depends on your application.

A rough estimate: $ \sum_{k=0}^n \binom{n}{k}^3 =\sum_{k=0}^n \binom{n}{k}^2 \binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor }\sum_{k=0}^n \binom{n}{k}^2 =\binom{n}{\lfloor n/2 \rfloor } \binom{2n}{n} \sim \frac{2^{3n+1/2} }{\sqrt{\pi n} } $

where we used $\displaystyle \sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n} $ (try to prove this) and the last estimate was done with Stirling's approximation. If this suffices for your problem, finish with the conclusion $\sum_{k=0}^n \binom{n}{k}^3 < \frac{2^{3n+1/2} }{\sqrt{3 n} }.$

However, judging from how rough the estimate was (the main loss of accuracy came from replacing all the $\displaystyle \binom{n}{k}$ with the largest term), we suspect we could easily (that is, tediously but with little creativity) show that in fact

$ \sum_{k=0}^n \binom{n}{k}^3 = \mathcal{o}\left( \frac{2^{3n+1/2} }{\sqrt{\pi n} } \right).$

However, if you are going to put that much effort in anyway, you might as well use these more precise estimates. Mike's one gives $\sum_{k=0}^n \binom{n}{k}^3 = \frac{2^{3n+1} }{\sqrt{3} \pi n} \left(1 + \mathcal{O} \left( n^{-1/2 + \epsilon}\right) \right) $

so our weak estimate is about $\sqrt{n} $ too large.

  • 2
    [OEIS A000172](https://oeis.org/A000172) also gives $\dfrac{2^{3n+1}}{\sqrt{3}\pi n}$.2012-04-21
4

As a complement to Ragib Zaman fine answer (and Henry's useful comment see for example Farmer and Leth's 'An asymptotic formula for powers of binomial coefficients' which contains, about a closed form for your sum, "..it has only recently been shown that no such formula can exist") let's add a more precise asymptotic expansion (this is conjectured only...) :

$\frac{\sum_{k=0}^n \binom{n}{k}^3}{\frac{2^{3n+1} }{\sqrt{3} \pi n}}=1 -\frac 1{3n}+\frac 1{3^3n^2}+\frac 1{3^4n^3}+\frac 1{3^5n^4}+\frac {11}{3^7 n^5}+\frac {49}{3^9 n^6}-\frac {317}{3^9 n^7}-\frac{2797}{3^{10} n^8}-\frac{61741}{3^{13} n^9}+\operatorname{O}\left(\frac 1{n^{10}}\right)$

  • 0
    @Henry: yes but true! :-) (rewritten with logs : $\log(\pi)+\frac{\log(3)}2-\log(2)\approx 1\ $)2012-04-21