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. 
 A: 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$.
A: 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.   
A: You can write
$$f_n=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{{\left\lfloor\frac{n+1}{2}\right\rfloor}+k\choose{\left\lfloor\frac{n}{2}\right\rfloor}-k}\quad(*)$$
Now, we'll prove that by induction:
First step, confirm $f_1,f_2$ true by $(*)$
Next, suppose $f_n$ true by $(*)$ we have must proof $f_{n+2}$ true by $(*)$
We'll done!
