A Problem with the Generating Function of Fibonacci.

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.

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.