# Thread: induction problem with fibonacci numbers

1. ## induction problem with fibonacci numbers

hi

here's another problem for the strong induction.
Prove that for all $n\ge 1$

$F_{2n-1}=\sum_{i=0}^{n-1}\;\binom{2n-i-2}{i}$

I let

$P(n)=\left[(n\ge 1)\Rightarrow\left(F_{2n-1}=\sum_{i=0}^{n-1}\;\binom{2n-i-2}{i}\right)\right]$

so the goal is

$\forall n[(\forall k

let n be arbitrary in N. Suppose

$\forall k

and since we have to prove P(n), also suppose

$n\ge 1$

I proved some base cases for n=1,2.so let's consider the case

$n \geqslant 3$

$\Rightarrow 1\leqslant n-1 < n$

so using inductive hypothesis,

$F_{2(n-1)-1}=\sum_{i=0}^{n-2}\;\binom{2(n-1)-i-2}{i}$

$F_{2n-3}=\sum_{i=0}^{n-2}\;\binom{2n-i-4}{i}$

but after this point, I got stuck. I can see that, using recurrence
relation for the Fibonacci numbers

$\because 2n-1\geqslant 2\quad \therefore F_{2n-1}=F_{2n-2}+F_{2n-3}$

can people give some hints ?

$\leftrightsquigarrow\leftrightsquigarrow$

2. ## Re: induction problem with fibonacci numbers

This requires some work to write down carefully, but it's not too hard. See this thread for some references.

3. ## Re: induction problem with fibonacci numbers

thanks makarov........will check that