# Sum of cubes of binomial coefficients

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.

• Given the question, I assume you are interested in the asymptotics for $n\to\infty$? – Fabian Apr 21 '12 at 11:28
• @Fabian: Yes. That's what I need. – Elena Apr 21 '12 at 11:30
• Just for fun, Mathematica spits out $\, _3F_2(-n,-n,-n;1,1;-1)$, the generalized Hypergeometric function. – Jackson Apr 21 '12 at 17:21

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.

• OEIS A000172 also gives $\dfrac{2^{3n+1}}{\sqrt{3}\pi n}$. – Henry Apr 21 '12 at 11:34

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)$$

• Following your link, it is mildly curious that $2e \approx \sqrt{3} \pi$ to within 0.1%. – Henry Apr 21 '12 at 13:35
• @Henry: yes but true! :-) (rewritten with logs : $\log(\pi)+\frac{\log(3)}2-\log(2)\approx 1\$) – Raymond Manzoni Apr 21 '12 at 13:44