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