<s>[INST] 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. 
 [/INST] 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.
</s>