# binomial coefficient

Prove that $$\frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}.$$ I tried already by induction over $k$ but i have problems showing the statement holds for $k=0$ or $k=1$.

-
See Concrete Mathematics, page 203. –  wj32 Nov 15 '12 at 8:34
I am also looking for a combinatorical proof of this identity. –  bronko Dec 7 '12 at 3:45

The methodology is that you have got to make the brackets as the form expandable as the sum of polynomials with binomial coefficients And guess the clues through differentiation. It works no matter what the k is

-
Thank you for your answer. I expanded the left hand side via binomial formula. The problem is that the sum on the left hand side only counts to k while the one on the right hand side counts to $\infty$. –  bronko Nov 22 '12 at 13:47
It does not matter. The infinity means the adding the terms together while the t is smaller than 1/4 . When adding all these terms together, we can see a Geometric Series there –  Raju Gujarati Nov 22 '12 at 14:05
I expanded the left hand side to $\sum_{n=0}^k\binom{k}{n}\left(\frac{1}{2t}\right)^k\frac{-\sqrt{1-4t})^{k-n-1}}‌​{2t}^{k-n}}$ but that's it. I do not know how to proceed. –  bronko Nov 24 '12 at 8:06
PLease edit your comment I really can't see the formula you have typed –  Raju Gujarati Nov 26 '12 at 1:53
$$\sum_{n=0}^k \binom{k}{n} \left( \frac{1}{2t} \right)^k (- \sqrt{1-4t})^{k-n-1} (2t)^{-k+n}$$ –  bronko Nov 26 '12 at 5:11

This can be shown using a variant of Lagrange Inversion. Introduce $$T(z) = w = \sqrt{1-4z}$$ so that $$z = \frac{1}{4} (1-w^2)$$ and $$dz = -\frac{1}{2} w.$$

Then we seek to compute $$[z^n] \frac{1}{T(z)} \left(\frac{1-T(z)}{2z}\right)^k = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{T(z)} \left(\frac{1-T(z)}{2z}\right)^k dz.$$

Using the substitution this becomes $$- \frac{1}{2\pi i} \int_{|w-1| = \epsilon} \frac{4^{n+1}}{(1-w^2)^{n+1}} \frac{1}{w} \left(\frac{1-w}{1/2(1-w^2)}\right)^k \frac{1}{2} w \; dw \\ = - \frac{1}{2} \frac{1}{2\pi i} \int_{|w-1| = \epsilon} \frac{4^{n+1}}{(1-w^2)^{n+1}} \left(\frac{2}{1+w}\right)^k dw \\ = - \frac{1}{2\pi i} \int_{|w-1| = \epsilon} \frac{1}{(1-w)^{n+1}} \frac{2^{2n+k+1}}{(1+w)^{n+k+1}} dw \\ = (-1)^n \frac{1}{2\pi i} \int_{|w-1| = \epsilon} \frac{1}{(w-1)^{n+1}} \frac{2^{2n+k+1}}{(1+w)^{n+k+1}} dw.$$

Now expand the second fraction about $w=1$ to get $$\frac{1}{(1+w)^{n+k+1}} = \frac{1}{(2+(w-1))^{n+k+1}} = \frac{1}{2^{n+k+1}} \frac{1}{(1+1/2(w-1))^{n+k+1}} \\ = \frac{1}{2^{n+k+1}} \sum_{q\ge 0} {q+n+k\choose q} (-1)^q \frac{(w-1)^q}{2^q}.$$

We need $q=n$ for the residue in the integral, getting the final answer $$(-1)^n \times 2^{2n+k+1} \times \frac{1}{2^{n+k+1}} {2n+k\choose n} (-1)^n \frac{1}{2^n} = {2n+k\choose n}.$$

This MSE link has another calculation that is quite similar.

-