0
$\begingroup$

Define $S_0=0, S_1=01$. Then for $n\geq 2$ we define $S_n=S_{n-1}S_{n-2}$ (concatenating the previous sequence and the one before that). We obtain a limiting sequence, which we call the inifinite Fibonacci word. The first few entries are given by

0100101001001 ...

According to this Wikipedia page:

In the infinite Fibonacci word, the ratio (number of letters)/(number of zeroes) is $\varphi$, as is the ratio of zeroes to ones.

$\varphi$ refers to the Golden Ratio. There is no citation given. How do we prove this?

$\endgroup$
3
$\begingroup$

Define $Z(n)$ as the number of zeros in the $n^{th}$ word and $Y(n)$ as the number of $1$s.
We get the recurrences $$Z(n)=Z(n-1)+Z(n-2)\\Y(n)=Y(n-1)+Y(n-2)$$ with the initial conditions $$Z(0)=1,Z(1)=1,Y(0)=0,Y(1)=1$$ The recurrence is the Fibonacci one and we can see that $Z(n)=Y(n-1)$=F(n). As the ratio of Fibonacci terms goes to the golden ratio we are home.

You can also use the general procedure for solving linear recurrence relations to show the number of ones and zeros grows by a factor $\phi$ every step.

$\endgroup$
  • 1
    $\begingroup$ I type too slow. +1 $\endgroup$ – SinTan1729 Aug 21 '18 at 5:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.