Sum of cubes of binomial coefficients

Solution 1:

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

Solution 2:

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.