Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Walters Apr 21 '12 at 17:21
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
2  
OEIS A000172 also gives $\dfrac{2^{3n+1}}{\sqrt{3}\pi n}$. –  Henry Apr 21 '12 at 11:34
add comment

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

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.