How can we show that the following (recursive) statement, where is the -th Fibonacci number, and , is true?

******

As this should be shown to be valid for every , I believe we can use induction. The least which has to satisfy the above equation is , so we take the case when as basis. But,

, because , and .

However, if we take the case when as basis, then the above statementistrue:

Is this problem wrongly posed? Should we show that is true for every instead of ?

And my next question would be how to proceed with the inductive step? I know we should use the fact that somewhere, but so far I couldn't show that the above is true for if we suppose it is valid form some .

I'll be immensely grateful for any help.