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 statement is true:
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.