First I'd like to TeX this so that others can read what you wrote. (Please consider writing your problem in LaTeX next time.) You are trying to show that for all integers (where ), that

I think that using induction is a fine idea. The only slight change I would make is to use strong induction, where we assume that the formula works for . The reason for this is that the Fibonnaci numbers are defined by the previous two terms in the sequence:

Weak induction would technically only allow us to say something about the term, but not the other term.

Technical details aside, to complete the induction, you tried to show that the formula works for , but got stuck. I recommend using that recursion relation above:

Now you have the induction assumption up to so you could write and using the formula. Try it out and see where it goes. (I haven't actually carried it out myself, but I would expect it to work.) Let us know how it turns out.