Ttdfjt

Some time ago a question was asked here regarding the value of the sum $$sum_i=0^k frac2i choose i4^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 2ichoose j$ also that $2i choose i=sum_j=0^i ichoose 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+frac12 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
beginalign*
[z^i]frac1sqrt1-4z=binom2iitag1
endalign*

We obtain
beginalign*
colorbluesum_i=0^kcolorbluebinom2iifrac14^i
&=sum_i=0^k[z^i]frac1sqrt1-ztag2\
&=[z^0]frac1sqrt1-zsum_i=0^kz^-itag3\
&=[z^0]frac1sqrt1-zcdotfracleft(frac1zright)^k+1-1frac1z-1tag4\
&=[z^k]frac1-z^k+1(1-z)^3/2tag5\
&=[z^k]sum_j=0^inftybinom-frac32j(-z)^jtag6\
&=[z^k]sum_j=0^inftybinomj+frac12jz^jtag7\
&,,colorblue=binomk+frac12k
endalign*

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-pq=binomp+q-1q(-1)^q$.




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

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 binom2ii
= 1 over 4^,i Gamma left( 2left( 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) = binomi-1/2i
$$

Then our sum is
$$
eqalign
& sumlimits_i = 0^k 1 over 4^,i left( matrix
2i cr
i cr right) = cr
& = sumlimits_i = 0^k left( matrix
i - 1/2 cr
i cr right) = quad quad (1) cr
& = sumlimits_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.

We prove that $$sum_k=0^n frac2k choose k4^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 =fraca_n2n+2 = frac(2n+1)!2(n+1)cdot n!^24^n = frac(2n+1)!(n+1)!n!4^n+1cdot 2\ = frac(2n+1)!(n+1)!n!4^n+1cdot frac2n+2n+1 = frac(2n+2)!(n+1)!^24^n+1 = frac2(n+1) choose n+14^n+1,$$
which is the added term in the summation. This completes the induction.