6
$\begingroup$

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!

$\endgroup$
10
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Very nice approach. (+1) $\endgroup$ – Markus Scheuer May 23 at 22:05
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 but the result wasn't known beforehand so I dont think induction can really help :) $\endgroup$ – Archis Welankar May 23 at 18:50
  • $\begingroup$ @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). $\endgroup$ – auscrypt May 23 at 18:52

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.