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.

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

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.

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

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

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

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.