Proof By Induction: Fibonacci Results

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.

• Just use the fact that $|f(n+1)|=|f(n)+|f(n-1)|$. – Brian M. Scott Oct 5 '16 at 22:06
• @BrianM.Scott how would i do that? – ShadowViper Oct 5 '16 at 22:11
• Your induction hypothesis tells you what $|f(n)|$ and $|f(n-1)|$ are; what are they? – Brian M. Scott Oct 5 '16 at 22:16
• well , |f(n)| = f(n+2) so |f(n-1)| = f(n+1)? So then |f(n+3)| = f(n+2) + f(n+1) right? but then what? – ShadowViper Oct 5 '16 at 22:21
• Not quite. First, let me correct the notation to use subscripts, since that’s how the notation was actually defined. Then $|f_n|=F_{n+2}$ and $|f_{n-1}|=F_{n-1}$: the $f_k$ are the words, and the $F_k$ are the numbers. Now what do you know about $F_{n+2}+F_{n+1}$? Use the definition of the Fibonacci sequence. – Brian M. Scott Oct 5 '16 at 22:30