induction problem with fibonacci numbers

**issacnewton** · October 5th 2011, 01:40 AM

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<n P(k))\Rightarrow P(n)]$

let n be arbitrary in N. Suppose

$\forall k<n P(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$

**emakarov** · October 5th 2011, 11:46 AM

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

**issacnewton** · October 5th 2011, 09:00 PM

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

Thread: induction problem with fibonacci numbers

LinkBack

Thread Tools

Display

induction problem with fibonacci numbers

Re: induction problem with fibonacci numbers

Re: induction problem with fibonacci numbers

Similar Math Help Forum Discussions

Math induction: Fibonacci Numbers

Induction Proof- Fibonacci Numbers

Induction with Fibonacci Numbers

Induction and Fibonacci Numbers

Help with induction for Fibonacci Numbers