induction problem with fibonacci numbers

hi

here's another problem for the strong induction.

Prove that for all

I let

so the goal is

let n be arbitrary in N. Suppose

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

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

so using inductive hypothesis,

but after this point, I got stuck. I can see that, using recurrence

relation for the Fibonacci numbers

can people give some hints ?

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.

Re: induction problem with fibonacci numbers

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