# Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

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

If we define $$f_n(t)=\sum_{k=0}^\infty\binom{2k+n}{k}t^k\tag{1}$$ then we have \begin{align} f_n'(t) &=\sum_{k=0}^\infty\binom{2k+n}{k}kt^{k-1}\\ &=\sum_{k=0}^\infty\binom{2k+n-1}{k-1}(2k+n)t^{k-1}\\ &=\sum_{k=0}^\infty\binom{2k+n+1}{k}(2k+n+2)t^k\\[6pt] &=(n+2)f_{n+1}(t)+2tf_{n+1}'(t)\tag{2} \end{align}

If we define \begin{align} g_n(t) &=\frac1{\sqrt{1-4t}}\left(\frac{1-\sqrt{1-4t}}{2t}\right)^n\\ &=\frac1{\sqrt{1-4t}}\left(\frac2{1+\sqrt{1-4t}}\right)^n\tag{3} \end{align} then we have $$g_n'(t) =\left(\frac{1}{\sqrt{1-4t}^3}+\frac{n+1}{1-4t}\right)\left(\frac2{1+\sqrt{1-4t}}\right)^{n+1}\tag{4}$$ and therefore \begin{align} &(n+2)g_{n+1}(t)+2tg_{n+1}'(t)\\[9pt] &=\frac{n+2}{\sqrt{1-4t}}\left(\frac2{1+\sqrt{1-4t}}\right)^{n+1}\\ &+2t\left(\frac{1}{\sqrt{1-4t}^3}+\frac{n+2}{1-4t}\right)\left(\frac2{1+\sqrt{1-4t}}\right)^{n+2}\\ &=\frac{n+2}{\sqrt{1-4t}}\left(\frac2{1+\sqrt{1-4t}}\right)^{n+1}\\ &+(1-\sqrt{1-4t})\left(\frac{1}{\sqrt{1-4t}^3}+\frac{n+2}{1-4t}\right)\left(\frac2{1+\sqrt{1-4t}}\right)^{n+1}\\ &=\left(\frac{1}{\sqrt{1-4t}^3}+\frac{n+1}{1-4t}\right)\left(\frac2{1+\sqrt{1-4t}}\right)^{n+1}\\[9pt] &=g_n'(t)\tag{5} \end{align}

Equations $(2)$ and $(5)$ ensure that \begin{align} f_n'(t)&=(n+2)f_{n+1}(t)+2tf_{n+1}'(t)=2t^{-\frac n2}\left[t^{\frac{n+2}{2}}f_{n+1}(t)\right]'\\ g_n'(t)&=(n+2)g_{n+1}(t)+2tg_{n+1}'(t)=2t^{-\frac n2}\left[t^{\frac{n+2}{2}}g_{n+1}(t)\right]' \end{align}\tag{6} Furthermore, it follows from $(1)$ and $(3)$ that $$f_n(0)=g_n(0)=1\tag{7}$$

The generalized binomial theorem yields \begin{align} (1-4t)^{-1/2} &=1+\frac124\frac{t}{1!}+\frac12\frac324^2\frac{t^2}{2!}+\frac12\frac32\frac524^3\frac{t^3}{3!}+\dots\\ &=\sum_{k=0}^\infty\frac{(2k-1)!!}{k!}2^kt^k\\ &=\sum_{k=0}^\infty\frac{(2k)!}{2^kk!k!}2^kt^k\\ &=\sum_{k=0}^\infty\binom{2k}{k}t^k\tag{8} \end{align} Equation $(8)$ ensures that $f_0(t)=g_0(t)$.

Equations $(6)$, $(7)$, and $(8)$ ensure that $$f_n(t)=g_n(t)\tag{9}$$ for all $n\ge0$. That is, $$\frac1{\sqrt{1-4t}}\left(\frac{1-\sqrt{1-4t}}{2t}\right)^n =\sum_{k=0}^\infty\binom{2k+n}{k}t^k\tag{10}$$

-
Nice, nice! (+1) –  Chris's sis the artist Jun 1 at 16:15

Due to a recent comment on my other answer, I took a second look at this question and tried to apply a double generating function. \begin{align} &\sum_{n=0}^\infty\sum_{k=-n}^\infty\binom{2n+k}{n}x^ny^k\\ &=\sum_{n=0}^\infty\sum_{k=n}^\infty\binom{k}{n}\frac{x^n}{y^{2n}}y^k\\ &=\sum_{n=0}^\infty\frac{x^n}{y^{2n}}\frac{y^n}{(1-y)^{n+1}}\\ &=\frac1{1-y}\frac1{1-\frac{x}{y(1-y)}}\\ &=\frac{y}{y(1-y)-x}\\ &=\frac1{\sqrt{1-4x}}\left(\frac{1+\sqrt{1-4x}}{1+\sqrt{1-4x}-2y}-\frac{1-\sqrt{1-4x}}{1-\sqrt{1-4x}-2y}\right)\\ &=\frac1{\sqrt{1-4x}}\left(\frac{1+\sqrt{1-4x}}{1+\sqrt{1-4x}-2y}+\color{#C00000}{\frac{2x/y}{1+\sqrt{1-4x}-2x/y}}\right)\tag{1} \end{align} The term in red contains those terms with negative powers of $y$. Eliminating those terms yields \begin{align} \sum_{n=0}^\infty\sum_{k=0}^\infty\binom{2n+k}{n}x^ny^k &=\frac1{\sqrt{1-4x}}\frac{1+\sqrt{1-4x}}{1+\sqrt{1-4x}-2y}\\ &=\frac1{\sqrt{1-4x}}\sum_{k=0}^\infty\left(\frac{2y}{1+\sqrt{1-4x}}\right)^k\\ &=\frac1{\sqrt{1-4x}}\sum_{k=0}^\infty\left(\frac{1-\sqrt{1-4x}}{2x}\right)^ky^k\tag{2} \end{align} Equating identical powers of $y$ in $(2)$ shows that $$\sum_{n=0}^\infty\binom{2n+k}{n}x^n=\frac1{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^k\tag{3}$$

-
(+1) Awesome!! :) –  r9m Jun 1 at 20:11
@Semiclassical: Not a typo. The terms with negative $k$ are those with negative powers of $y$ that were eliminated with the red term in $(1)$. –  robjohn Jun 2 at 20:44

We proceed by induction on $k$.

For $k = 0$, we have $\displaystyle \sum\limits_{m=0}^{\infty} \binom{2m}{m}t^m = \frac{1}{\sqrt{1-4t}}$

and for $k = 1$, we have

\begin{align*} \sum\limits_{m=0}^{\infty} \binom{2m+1}{m+1}t^m &= \sum\limits_{m=0}^{\infty} \left(2 - \frac{1}{m+1}\right)\binom{2m}{m}t^m \\&= \frac{2}{\sqrt{1-4t}} - C(t)\\&= \frac{2}{\sqrt{1-4t}} -\frac{2}{1+\sqrt{1-4t}} \\&= \frac{2}{\sqrt{1-4t}(1+\sqrt{1-4t})}\end{align*}

Where, $\displaystyle C(t) = \sum\limits_{m=0}^{\infty} \frac{1}{m+1}\binom{2m}{m}z^m = \frac{2}{1+\sqrt{1-4t}}$ is the generating function of Catalan Numbers.

Assuming the result holds for $k$ we prove for $k+1$:

\begin{align*}\sum\limits_{m=0}^{\infty} \binom{2m+k+1}{m+k+1}t^m &= \sum\limits_{m=0}^{\infty} \left(2 - \frac{k+1}{m+k+1}\right)\binom{2m+k}{m+k}t^m\\ &= \frac{2^{k+1}(1+\sqrt{1-4t})^{-k}}{\sqrt{1-4t}} - \frac{k+1}{t^{k+1}}\int_0^t \sum\limits_{m=0}^{\infty} \binom{2m+k}{m+k}t^{m+k}\,\mathrm{d}t\\ &= \frac{2^{k+1}(1+\sqrt{1-4t})^{-k}}{\sqrt{1-4t}} - \frac{2^k(k+1)}{t^{k+1}}\int_0^t \frac{t^k(1+\sqrt{1-4t})^{-k}}{\sqrt{1-4t}}\,\mathrm{d}t\\ &= \frac{2^{k+1}(1+\sqrt{1-4t})^{-k}}{\sqrt{1-4t}} - \frac{k+1}{2^kt^{k+1}}\int_0^t \frac{(1-\sqrt{1-4t})^{k}}{\sqrt{1-4t}}\,\mathrm{d}t\\ &= \frac{2^{k+1}(1+\sqrt{1-4t})^{-p}}{\sqrt{1-4t}} - \frac{k+1}{2^{k+1}t^{k+1}} \frac{(1-\sqrt{1-4t})^{k+1}}{k+1}\\ &= \frac{2^{k+1}(1+\sqrt{1-4t})^{-k}}{\sqrt{1-4t}} - 2^{k+1}(1+\sqrt{1-4t})^{-(k+1)}\\ &= \frac{2^{k+1}(1+\sqrt{1-4t})^{-(k+1)}}{\sqrt{1-4t}}\\ \end{align*}

-
Very nice and simple! (+1) –  Chris's sis the artist Jun 1 at 16:15


With $\ds{0\ <\ t\ <\ {1 \over 4}}$: \begin{align}&\color{#c00000}{\sum_{n = 0}^{\infty}{2n + k \choose n}t^{n}} =\sum_{n = 0}^{\infty}\bracks{\oint_{\verts{z}\ =\ 1^{+}}{\pars{1 + z}^{2n + k} \over z^{n + 1}}% \,{\dd z \over 2\pi\ic}}t^{n} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{+}}{\pars{1 + z}^{k} \over z}\sum_{n = 0}^{\infty} \bracks{\pars{1 + z}^{2}\,t \over z}^{n}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1^{+}}{\pars{1 + z}^{k} \over z} {1 \over 1 - \pars{1 + z}^{2}\,t/z}\,{\dd z \over 2\pi\ic} \\[5mm]&=-\,{1 \over t}\oint_{\verts{z}\ =\ 1^{+}} {\pars{1 + z}^{k} \over z^{2} + \pars{2 - 1/t}z + 1} \,{\dd z \over 2\pi\ic} =-\,{1 \over t}\oint_{\verts{z}\ =\ 1^{+}} {\pars{1 + z}^{k} \over \pars{z - z_{-}}\pars{z - z_{+}}}\,{\dd z \over 2\pi\ic} \end{align}

where $\ds{z_{\pm}}$ are the roots of $\ds{z^{2} + \pars{2 - {1 \over t}}z + 1 = 0}$: $$z_{\pm} = {1 \pm \root{1 - 4t} - 2t \over 2t}$$ such that $\ds{z_{+} > 1}$ and $\ds{\verts{z_{-}} < 1}$.

Then, \begin{align}&\color{#c00000}{\sum_{n = 0}^{\infty}{2n + k \choose n}t^{n}} =-\,{1 \over t}\,{\pars{1 + z_{-}}^{k} \over z_{-} - z_{+}} =-\,{1 \over t}\pars{-\,{t \over \root{1 - 4t}}} \pars{1 + {1 - \root{1 - 4t} - 2t\over 2t}}^{k} \end{align}

which simplifies to $$\color{#66f}{\large% {1 \over \root{1 - 4t}}\,\pars{1 - \root{1-4t} \over 2t}^{k} =\sum_{n = 0}^{\infty}{2n + k \choose n}t^{n}}$$

-

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 \; dw.$$

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.

-