# 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$.

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.

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!