we form generating function of $ \sum_{k = 1}^n\binom{n + k - 1}{2k - 1}$ $ \sum_{n\geq0}x^n\sum_{k = 1}^n\binom{n + k - 1}{2k - 1}$=$ \sum_{k\geq0}\sum_{n}\binom{n + k - 1}{2k - 1}x^n$=$ \sum_{k\geq0}x^{1 - k}\sum_{n}\binom{n + k - 1}{2k - 1}x^{n + k - 1}$=$ \sum_{k\geq0}x^{1 - k}\sum_{r}\binom{r}{2k - 1}x^r$=$ \sum_{k}x^{1 - k}\times \frac {x^{2k - 1}}{(1 - x)^{2k}}$=$ \sum_{k}(\frac {x}{(1 - x)^2})^k$=$ \frac {(1 - x)^2}{1 - 3x - x^2}$ but if we open $ {1 - 3x - x^2}$ we will see that the root of $ {1 - 3x - x^2}$ are the squares of root of $ 1 - x - x^2$ as we know that $ f_{n}$=$ \frac {\alpha^n - \beta^n}{\sqrt5}$ where $ \alpha$ and$ \beta$ are root of $ 1 - x - x^2$ after opening $ \frac {1}{1 - 3x - x^2}$as generating form we get to the point

I have another approach. Let $ f_k$ be the number of ways to tile a $ k$-board using one-tiles and two-tiles. Then $ f_k=F_{k+1}$ where $ F_{k+1}$ is the $ (k+1)^{th}$ term of the fibonacci sequence. Specifically, $ F_{2n}=f_{2n-1}$. So let's count the number of ways there are to tile a $ (2n-1)$ board. As indicated above, there are $ f_{2n-1}$ ways. But let us count these tilings in another way. Since the length of the board is an odd number we know there is at least one $ 1$-tile. Furthermore there is always an odd number of $ 1$-tiles. Say there are $ 2k-1$ $ 1$-tiles, then there are $ 2n-1-(2k-1)=2(n-k)$ tiles left on the board which can be covered with $ n-k$ $ 2$-tiles. In all there are $ (2k-1)+(n-k)=n+k-1$ tiles from which we are selecting $ 2k-1$ of them (the $ 1$-tiles) for placement. There are $ \displaystyle \binom{n+k-1}{2k-1}$ ways. Summing over all possible $ k$, we have $ \displaystyle \sum_{k=1}^n \binom{n+k-1}{2k-1}=f_{2n-1}=F_{2n}$ as desired.

it is very easy if we use snake oil method...

Note that $\sum_{n+k=m}{\dbinom{n}{k}}$ denotes the $m+1$th fibonacci number.This is easy to see by by induction on $m$ and noting the fact that $F_{m+2}=F_{m+1}+F_{m}=\sum_{n+k=m}{\dbinom{n}{k}}+\sum_{n+k=m-1}{\dbinom{n}{k}}=\sum_{n+k=m}{\dbinom{n}{k}+\dbinom{n}{k-1}}=\sum_{n+k=m}{\dbinom{n+1}{k}}=\sum_{n+k=m+1}{\dbinom{n}{k}}$ where we have used the induction hypothesis assuming the statement to be true for all integers upto $m+1$.Now $\sum_{k=1}^{n}{\dbinom{n+k-1}{2k-1}}=\sum_{k=1}^{n}{\dbinom{n+k-1}{n-k}}=\sum_{j+k=2n-1}{\dbinom{j}{k}}=F_{2n}$

This problem is a good example of showcasing the power of generating functions. My solution if basically the same as #$2$, but I am still posting it for completeness. $\text{Sol}^n$. It is sufficient to show that : $$\sum_{n \ge 0} \sum_{k=1}^{n} \dbinom {n+k-1}{2k-1} X^n = \sum_{n \ge 0} F_{2n} X^n$$ $\bullet$ The Left hand side factors as: \begin{align*} \sum_{k=1}^{n} \dbinom {n+k-1}{2k-1} & = \sum_{k \ge 1} \sum_{n \ge 0} \dbinom{n+k-1}{2k-1} X^n\\& = \sum_{k \ge 1} X^{1-k} \sum_{n \ge 0} \dbinom{n+k-1}{2k-1} X^{n+k-1}\\& = \sum_{k \ge 1} X^{1-k} \cdot \dfrac {X^{2k-1}}{(1-X)^{2k}} \\& = \dfrac {X}{1-3X +X^2} \end{align*} $\bullet$ Now factoring the Right hand side is easy using the Binet's formula : $F_n = \dfrac{1}{\sqrt{5}}\cdot ( \phi ^{n} - \phi ^{-n}))$. \begin{align*} \sum_{n \ge 0} F_{2n} X^n & = \sum_{n \ge 0} \dfrac{1}{\sqrt{5}} \cdot ( \phi ^{2n} - \phi ^{-2n}) X^n \\& = \dfrac {1}{\sqrt{5}} \cdot ( \dfrac {1}{1- \phi ^2X }- \dfrac {1}{1- \phi ^{-2}X})\\& = \dfrac {X}{1 - 3X + X^2} \blacksquare \end{align*}

Another similar one: Prove that $$\sum_{i=1}^{n}\left(\sum_{k=0}^{2i-2}\binom{2i-k-2}{k}\right)=F_{2n}$$

?$\color{white}\textbf{anyone?}$