A Problem with the Generating Function of Fibonacci. 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. 
 A: 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.
A: 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.
