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.