# Asymptotics for sum of binomial coefficients from Concrete Mathematics

Concrete Mathematics EXERCISE 9.25:

Supposing $S_n = \sum_{k=0}^n \binom{3n}k$ Prove that $S_n = \binom{3n}{n}\left(2-\frac4n+O\left(\frac1{n^2}\right)\right)$

This sequence also appears in OEIS A066380

I have been trying to understand the answer to the problem, but failed:

$S_n\left/\binom{3n}n\right. = \sum_{k=0}^n \frac{n\cdots(n-k+1)}{(2n+1)\cdots(2n+k)}\tag1$ We may restrict the range of summation to $0 \le k \le (\log n)^2$, say. In this range $n\cdots(n-k+1) = n^k\left(1-\binom k2/n+O(k^4/n^2)\right)$ and $(2n+1)\cdots(2n+k) = (2n)^k\left(1+\binom{k+1}2/2n+O(k^4/n^2)\right)$, so the summand is $\frac1{2^k}\left(1-\frac{3k^2-k}{4n}+O\left(\frac{k^4}{n^2}\right)\right) \tag2$ Hence the sum over $k$ is $2-4/n+O(1/n^2)\tag3$ Q.E.D.

The formula (1) is acceptable, because $\left. \binom{3n}{n-k} \right/ \binom{3n}{n} = \frac{n\cdots(n-k+1)}{(2n+1)\cdots(2n+k)}$ The equation (2) maybe holds for $0 \le k \le (\log n)^2$, but formula (3) seems too strange (notice that $k$ is restricted, not over integers from $[0..n]$. How can we conclude that?

I have tried to considered equation (2) as the partial sum of a power series (the Taylor series for $n^{-1}$), but there seems no evidence that the corresponding power series of (2) or (3) converges.

Now OP has understood the answer. A trivial trick is necessary. OP will look for someone clever to give a complete solution and set his/her answer as accepted answer.

• I don't understand your last sentence. Certainly if you sum (2) over all $k$, it converges. For any fixed integer $r$, the sum on $k$ of $k^r/2^k$ converges. – Gerry Myerson Jun 8 '12 at 12:23
• @GerryMyerson I meant that (2) is really a power series of $n^{-1}$ (Taylor series), for all $k$ not only when $0 \le k \le (\log n)^2$, and the O-notation shows the first 2 terms of it, but I can't check the power series converges, for the equation (3), which is the sum of equation (2). – Yai0Phah Jun 8 '12 at 13:44

The claim is that $$\sum_{k=0}^{m} \frac1{2^k}\left(1-\frac{3k^2-k}{4n}+O\left(\frac{k^4}{n^2}\right)\right) = 2-4/n+O(1/n^2)$$ where $m=\lfloor \log_2^2 n \rfloor.$
Computing one term at a time: $\displaystyle A(m)= \sum_{k=0}^m 1/2^k = 2 - 2^{-m}= 2- \frac{1}{n^{\log n}}= 2 + \mathcal{O}(n^{-2}).$
This far into the book you should know how to compute $\displaystyle \sum_{k=0}^m \frac{3k^2-k}{2^k} = \frac{ 2^{m+4} -3m^2-11m-16}{2^m}.$ (In case you forgot, try differentiating $\sum x^m/2^m$.) The only thing that survives the $\mathcal{O}(n^{-2})$ war is $2^4=16$ so the second term contributes $-4/n + \mathcal{O}(n^{-2}).$
And finally, $\displaystyle \sum_{k=1}^{\infty} \frac{k^4}{2^k}$ is convergent so the last terms contribution is certainly $\mathcal{O}(n^{-2}).$ Hence the result.
• The claim is not $\sum_{k=0}^m$ but $\sum_{k=0}^n$. The tail should be estimated. Another trick: You can do sum on $\sum_{k\ge0}2^{-k}\left(1-\frac{3k^2-k}{4n}\right)$ then substract $\sum_{k>m}2^{-k}\left(1-\frac{3k^2-k}{4n}\right)$, the second one is extremely small, so it is not neccessary to evaluate its exact value (it can be evaluated as you showed, but such evaluating usually causes mistakes), and we only need to find an asymptotics. – Yai0Phah Jun 9 '12 at 3:57