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$