Solution check: Let $f_n$ be fibonacci numbers. Prove: $\sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1}$ and $\sum_{k=0}^n \binom{n+k}{2k} = f_{2n}$ The question: Let $f_n$ be fibonacci numbers. Prove: $\sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1}$ and $\sum_{k=0}^n \binom{n+k}{2k} = f_{2n}$
For every $n\in N$.
$f_0=f_1=1$, $f_n=f_{n-1}+f_{n-2}$ for $n\ge 2$
I'm supposed to do this through induction.
What I did, first, is that I've seen that for $1$ both statements are true, then assumed for $n$.
For $n+1$ I got that the first sum is equal to the first sum for $n$ and the second sum for $n$, which under the definition of fibonacci numbers, makes the assumption true.
Similarly I did the process for the second sum.
Is this all that I had to do to solve this problem? What's bugging me is that I need to use both of the sums for a certain $n$ in proving that either one of those sums is valid for $n+1$, which I haven't encountered yet in exercises containing induction. 

Yes, that is right. Note that you are saying is the following: the inductive statement is
$$P(n): \sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1} \, \mbox{ and } \, \sum_{k=0}^n \binom{n+k}{2k} = f_{2n}$$
Thus, when you prove $P(n) \Rightarrow P(n+1)$ you assume that both equalities hold for $n$ and you prove them both (one at a time) for $n+1$.
