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?
Best Answer
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.