# induction problem with fibonacci numbers

• Oct 5th 2011, 01:40 AM
issacnewton
induction problem with fibonacci numbers
hi

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

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

I let

$\displaystyle 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

$\displaystyle \forall n[(\forall k<n P(k))\Rightarrow P(n)]$

let n be arbitrary in N. Suppose

$\displaystyle \forall k<n P(k)$

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

$\displaystyle n\ge 1$

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

$\displaystyle n \geqslant 3$

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

so using inductive hypothesis,

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

$\displaystyle 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

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

can people give some hints ?

$\displaystyle \leftrightsquigarrow\leftrightsquigarrow$
• Oct 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.
• Oct 5th 2011, 09:00 PM
issacnewton
Re: induction problem with fibonacci numbers
thanks makarov........will check that