1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Just use the fact that $|f(n+1)|=|f(n)+|f(n-1)|$. $\endgroup$ – Brian M. Scott Oct 5 '16 at 22:06
  • $\begingroup$ @BrianM.Scott how would i do that? $\endgroup$ – ShadowViper Oct 5 '16 at 22:11
  • $\begingroup$ Your induction hypothesis tells you what $|f(n)|$ and $|f(n-1)|$ are; what are they? $\endgroup$ – Brian M. Scott Oct 5 '16 at 22:16
  • $\begingroup$ 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? $\endgroup$ – ShadowViper Oct 5 '16 at 22:21
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Oct 5 '16 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.