Let say that the Fibonacci numbers are defined recursively by
F_0 = 0
F_1 = 1
F_(n+1) = F_n + F_(n-1), n >= 1
and the Fibonacci words are defined by the recurrence relation
f_0 = a
f_1 = ab
f_(n+1) = f_n f_(n-1)
Then, how would I prove the following results by induction?
|f_n| = F_(n+2)
This is what I have done so far. I have shown that the basis step is true for the value of n = 2 and declared an inductive hypothesis. However, from there I am not sure how I would prove the result in the inductive step. I know that i would have to prove that it would be true for any value k+1 where n = k+1, but from there, I am having trouble showing it.
BASIS:
Let’s assume n = 2 and f(n) = f(n-1) * f(n-2) and f(1) = ab, f(0) = a then;
f(n):
|f(2)| = |f(1) * f(0)|
= |ab * a|
= |3|
f(n+2):
|f(4)| = |f(3) + f(2)|
= |f(2) + f(1) + f(2) |
= |f(1) + f(0) + f(1) + f(1) + f(0) + f(0) |
= |1 + 0 + 1 + 1 + 0|
= |3|
Therefore, f(n) = f(n+2) is true
INDUCTIVE HYPOTHESIS: Suppose |f(n)| = f(n+2) for all value of n >= 0.