# induction problem with fibonacci numbers

• October 5th 2011, 01:40 AM
issacnewton
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$
• October 5th 2011, 11:46 AM
emakarov
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.
• October 5th 2011, 09:00 PM
issacnewton
Re: induction problem with fibonacci numbers
thanks makarov........will check that