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.
Hmmm. I tried it this way, as you suggested, and broke the problem down into the cases when is even or odd. But in each of those cases, in the inductive step, there would be , the number of different parity than that of .
For example, if some is odd, then
becomes
.
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 .)