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.