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. 

It might be easier to understand if stated using logic symbols. Let $n \in \mathbb N$. Dente by $P(n)$ the statement 
$$
\sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1} \quad \bigwedge \quad \sum_{k=0}^n \binom{n+k}{2k} = f_{2n}.
$$
You want to prove the statement $\forall \, n \in \mathbb N \ \ P(n)$. 
The base case is $1=1 \wedge 2=2$. The inductive step is, for arbitrary $k \in \mathbb N$, to prove $P(k) \Rightarrow P(k+1)$; what you did.   
