Value of the binomial series $\sum_{i=0}^k \frac{{2i \choose i}}{4^i}$

Some time ago a question was asked here regarding the value of the sum $$\sum_{i=0}^k \frac{{2i \choose i}}{4^i}$$. But it was deleted later by the OP. I went around it but didn't find a solution. Some common combinatoric identities I know of are $$4^i=2^{2i}=\sum_{j=0}^{2i} {2i\choose j}$$ also that $${2i \choose i}=\sum_{j=0}^{i} {i\choose j}^2$$. But they were hardly of any use. I also thought of individual term as probability but turns out I can't think of it as anything sensible.a quick WA check gave the answer as $${k+\frac{1}{2} \choose k}=\frac{(2k+1)!}{k!^24^k}$$ Help would be appreciated!

We use the coefficient of operator $$[z^n]$$ to denote the coefficient of $$z^n$$ of a series. Recalling the generating function of the central binomial coefficients we can write \begin{align*} [z^i]\frac{1}{\sqrt{1-4z}}=\binom{2i}{i}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{k}}\color{blue}{\binom{2i}{i}\frac{1}{4^i}} &=\sum_{i=0}^{k}[z^i]\frac{1}{\sqrt{1-z}}\tag{2}\\ &=[z^0]\frac{1}{\sqrt{1-z}}\sum_{i=0}^{k}z^{-i}\tag{3}\\ &=[z^0]\frac{1}{\sqrt{1-z}}\cdot\frac{\left(\frac{1}{z}\right)^{k+1}-1}{\frac{1}{z}-1}\tag{4}\\ &=[z^k]\frac{1-z^{k+1}}{(1-z)^{3/2}}\tag{5}\\ &=[z^k]\sum_{j=0}^\infty\binom{-\frac{3}{2}}{j}(-z)^j\tag{6}\\ &=[z^k]\sum_{j=0}^\infty\binom{j+\frac{1}{2}}{j}z^j\tag{7}\\ &\,\,\color{blue}{=\binom{k+\frac{1}{2}}{k}} \end{align*}

and the claim follows.

Comment:

• In (2) we apply the coefficient of operator according to (1).

• In (3) we use the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$.

• In (4) we apply the finite geometric series formula.

• In (5) we do some simplifications and apply the rule from (3) again.

• In (6) we observe $$z^{k+1}$$ in the numerator does not contribute to $$[z^k]$$ and we make a binomial series expansion.

• In (7) we use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$.

• In (8) we finally select the coefficient of $$z^k$$.

• the "coefficient of" method is always effective ! (+1) – G Cab May 23 at 21:42
• @GCab: At least often useful. :-) Thanks for the credit. – Markus Scheuer May 23 at 22:04

In another way, using the duplication formula for Gamma $$\Gamma \left( {2\,z} \right) = {{2^{\,2\,z - 1} } \over {\sqrt \pi }}\Gamma \left( z \right)\Gamma \left( {z + 1/2} \right) = 2^{\,2\,z - 1} {{\Gamma \left( z \right)\Gamma \left( {z + 1/2} \right)} \over {\Gamma \left( {1/2} \right)}}$$ we have $${1 \over {4^{\,i} }}\binom{2i}{i} = {1 \over {4^{\,i} }}{{\Gamma \left( {2\left( {i + 1/2} \right)} \right)} \over {\Gamma \left( {i + 1} \right)^{\,2} }} = {{\Gamma \left( {i + 1/2} \right)} \over {\Gamma \left( {1/2} \right)\Gamma \left( {i + 1} \right)}} = \binom{i-1/2}{i}$$

Then our sum is \eqalign{ & \sum\limits_{i = 0}^k {{1 \over {4^{\,i} }}\left( \matrix{ 2i \cr i \cr} \right)} = \cr & = \sum\limits_{i = 0}^k {\left( \matrix{ i - 1/2 \cr i \cr} \right)} = \quad \quad (1) \cr & = \sum\limits_i {\left( \matrix{ k - i \cr k - i \cr} \right)\left( \matrix{ i - 1/2 \cr i \cr} \right)} = \quad \quad (2) \cr & = \left( \matrix{ k + 1/2 \cr k \cr} \right)\quad \quad (3) \cr} where:
1) for the identity above;
2) replacing the sum upper bound with the first b., the lower bound is implicit in the second b.;
3) using the "double convolution" formula for binomials.

• Very nice approach. (+1) – Markus Scheuer May 23 at 22:05

We prove that $$\sum_{k=0}^{n} \frac{{2k \choose k}}{4^k} = \frac{(2n+1)!}{n!^24^n}.$$ We proceed by induction. The base case is easily verifiable. Denote the RHS of the above equation as $$a_n$$. Now consider $$a_{n+1} = \frac{(2n+3)!}{(n+1)!^24^{n+1}} = \frac{(2n+2)(2n+3)}{4(n+1)^2} \cdot \frac{(2n+1)!}{n!^24^n} = \frac{(2n+3)}{2n+2} a_n.$$ So we now have $$a_{n+1} - a_n =\frac{a_n}{2n+2} = \frac{(2n+1)!}{2(n+1)\cdot n!^24^n} = \frac{(2n+1)!}{(n+1)!n!4^{n+1}}\cdot 2\\ = \frac{(2n+1)!}{(n+1)!n!4^{n+1}}\cdot \frac{2n+2}{n+1} = \frac{(2n+2)!}{(n+1)!^24^{n+1}} = \frac{{2(n+1) \choose n+1}}{4^{n+1}},$$ which is the added term in the summation. This completes the induction.

• +1 but the result wasn't known beforehand so I dont think induction can really help :) – Archis Welankar May 23 at 18:50
• @ArchisWelankar Yeah, induction is only really useful here because the result was worked out already, either by guessing it or by using WA (or some other method). – auscrypt May 23 at 18:52