A Problem with the Generating Function of Fibonacci.

Question

So basically I want to find the closed form of $G_n = \sum_{k = 1}^n \binom{n+k - 1}{2k-1}$.

After checking for $n = 1,2,3,4$ the values are $1, 3, 8, 21$ respectively. I claim that it is $F_{2n}$ where $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$. My idea was to prove this using generating functions.

We have that $\binom{n+k-1}{2k-1}$ is the $n$th coefficient of $X^k \sum_{i \geq 0} \binom{i + 2k - 1}{i} X^i = \frac{X^k}{(1-X)^{2k}}$ so the $$\sum_{n \geq 0} G_n X^n = \sum_{k = 1}^n \frac{X^k}{(1-X)^{2k}}$$

Now we want to find what $F_0 + F_2X + F_4X^2 + ...$ is and we know that $F_0 + F_1X + ... = \frac{X}{1-X-X^2}$.

So \begin{align*} F_0 + F_2X^2 + F_4X^4 + ... & = \frac{1}{2} \left ( \frac{X}{1-X-X^2} + \frac{-X}{1 + X - X^2} \right ) \\ & = \frac{X^2}{(1-X^2)^2 - X^2} \end{align*} which means $$F_0 + F_2X + F_4X^2 + ... = \frac{X}{(1-X)^2 - X}.$$

So if suffices to show \begin{align*} \frac{X}{(1-X)^2 - X} & = \sum_{k = 1}^n \frac{X^k}{(1-X)^{2k}} \\ \frac{1}{(1-X)^2 - X} & = \sum_{k = 1}^n \frac{X^{k-1}}{(1-X)^{2k}} \\ \frac{(1-X)^{2n}}{(1-X)^2 - X} & = ((1-X)^2)^{n-1} + ((1-X)^2)^{n-2}X + ... + X^{n-1} \\ \frac{(1-X)^{2n}}{(1-X)^2 - X} & = \frac{(1-X)^{2n} - X^n}{(1-X)^2 - X} \end{align*} which is not true. I don't see where I went wrong with this.

Answer 1

Hint: There is just a small calculation error when transforming $\binom{n+k-1}{2k-1}$.

We obtain \begin{align*} \sum_{n=0}^\infty G_nx^n&=\sum_{n=0}^\infty\sum_{k=1}^n\binom{n+k-1}{2k-1}x^n\\ &=\sum_{k=1}^\infty\sum_{n=k}^\infty\binom{n+k-1}{2k-1}x^n\tag{1}\\ &=\sum_{k=1}^\infty\sum_{n=0}^\infty\binom{n+2k-1}{2k-1}x^{n+k}\tag{2}\\ &=\sum_{k=1}^\infty x^k\sum_{n=0}^\infty\binom{-2k}{n}(-x)^n\tag{3}\\ &=\sum_{k=1}^\infty \frac{x^k}{(1-x)^{2k}}\tag{4}\\ &=\frac{\frac{x}{(1-x)^2}}{1-\frac{x}{(1-x)^2}}\tag{5}\\ &=\frac{x}{1-3x+x^2}\\ &=x+3x^2+8x^3+21x^4+55x^5+144x^6+\cdots=\sum_{n=1}^\infty F_{2n}x^n \end{align*}

and the claim follows according to OPs expectation.

Commment:

• In (1) we exchange the summation order.

• In (2) we shift the index of the inner series by $k$.

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

• In (4) we use the binomial series expansion.

• In (5) we apply the geometric series expansion.

Answer 2

Suppose we seek the closed form of

$$G_n = \sum_{k=1}^n {n+k-1\choose 2k-1}.$$

Observe that the binomial coefficient

$${n+k-1\choose 2k-1} = {n+k-1\choose n-k}$$

has the property that its integral representation

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} (1+z)^{n+k-1} \; dz$$

vanishes when $k\gt n$ and also when $k=0$ ($[z^n] (1+z)^{n-1} = 0$). Therefore we can set the range of the sum from $k=0$ to infinity, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n-1} \sum_{k\ge 0} z^k (1+z)^k \; dz$$

which converges for $|z(1+z)|<1$ to yield

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n-1} \frac{1}{1-z(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{(1+z)^2} \frac{1}{1-z(1+z)} \; dz.$$

Putting $z/(1+z) = w$ we get $z = w/(1-w),$ $1+z=1/(1-w),$ $z(1+z) = w/(1-w)^2,$ and $dz = 1/(1-w)^2 dw$ which yields

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1-w)^2 \frac{1}{1-w/(1-w)^2} \frac{1}{(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w/(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1-2w+w^2}{1-3w+w^2} \; dw.$$

Recognizing the generating function of $F_{2n}$ which is

$$\frac{w}{1-3w+w^2}$$

we get

$$F_{2n+2} - 2 F_{2n} + F_{2n-2} \\ = F_{2n+1} + F_{2n} - 2 F_{2n} + F_{2n} - F_{2n-1} \\ = F_{2n} + F_{2n-1} + F_{2n} - 2 F_{2n} + F_{2n} - F_{2n-1} = F_{2n}$$

and we are done. The difference in these two generating function is the constant term which produces a value of one in the second generating function.