1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.