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.
For example, if some is odd, then
Let's say we have some odd number, for example n=5. In that case, , which is perfectly clear.
But in the inductive step, we take n=6 instead of n=5 and have which is meaningless (how to sum to -th term?).
Or do we, in the inductive step, take (when is odd, then is also odd). But then, on the right side of the equation, should become , while we need to have to prove this problem...
(Essentially, in the inductive proof we'd have to show that if
is true for some , then it is also true for .)