Showing that a sequence is greater than the Fibonacci sequence.

Let $X\subset\{0,1\}^\mathbb Z$ be the set consisting of all sequences with the property that any entry of value $1$ is followed by a non-zero even number of entries with value $0$. I.e if $x_i=1$ then $x_{i+1},\dots x_{i+2n}=0$ for some $n\geq 1$. Let $W_n(X)$ be the set of all allowable words in $X$ of length $n$. Specifically an element of $W_n(X)$ is an $n$-tuple $(\alpha_1,\dots,\alpha_n)$ such that there exists a $x\in X$ with the property that $x_{i+k}=\alpha_k$ for some $i\in \mathbb Z$ and $k\in \{0,\dots, n-1\}$.

Do we have something akin to a Fibonacci structure on the sequence $(|W_n(X)|)$? I.e $|W_n(X)|= |W_{n-1}(X)|+|W_{n-2}(X)|$, where equality may be replaced by an inequality and maybe some simple function with those terms as arguments? I ask because I am interested in $X$ as a subshift dynamical system, and I have heard that the topological entropy was $\log\varphi$, where $\varphi$ is the golden ratio. As $\varphi$ is the limit of $F_{n+1}/F_n$, where $F$ is the Fibonacci sequence, and $h(X)=\lim_{n\to \infty}\frac{1}{n}\log |W_n(X)|$, it seemed that if we could get prove some kind of Fibonacci structure on the sequence $(|W_n(X)|)$ I'd be halfway to seeing why the entropy is what it is. In fact using basic symbolic dynamics, and knowing that this "even" system is a sofic shift I have been able to show that $h(\sigma|_X)\leq \log \varphi$. Assuming that $|W_n(X)|\geq |W_{n-1}(X)|+|W_{n-2}(X)|$ I am able to derive the reverse inequality. Now I just need to prove this inequality.

I have tried to use induction for a while now, with no success. Any ideas, proofs, hints would be appreciated.

This type of shift is sometimes called the even shift. It is related with the so called golden mean shift. You can find a calculation of the entropy on the book "An introduction to symbolic dynamics and coding" by Douglas Lind and Brian Marcus. This is done in chapter 4, examples 4.1.4 and 4.1.6. These shifts are defined since chapter one, so there might be a few notations that they use defined in previous chapters.

They first calculate the entropy of the golden mean shift. The idea is to count the number of words of the shift by looking at the graph that correspond to this shift. To really count the growth of the number of words, one looks at the adjency matrix of this graph, the largest eigenvalue of that matrix will be the golden ratio, that is where you will see the golden ratio the first time in the calculation. You are correct that the number of words will grow as the Fibonacci sequence.

The calculation of the entropy of the even shift will be reduced to the calculation of the golden mean shift.

The details can be found in the reference given above.

• Thanks for the reference. Unfortunately their solution uses a lot more symbolic dynamics than what I've been exposed to. Nov 6, 2017 at 16:40

I have managed to come up with a solution using similar methods to the one I was thinking of to find a desired lower bound of the entropy. (It's very late where I am, so I'm hoping my claim of solution is correct).

If $w_n$ is the set consisting of all words of length $n$ in $X$ ending with either $1$ or $00$, then we claim that $|w_n|\geq |w_{n-1}|+|w_{n-2}|$ for all $n\geq 3$. To see this note that we can extend any word in $w_{n-2}$ to a word in $w_n$ simply by appending $00$ to the end of the word. Let $A\subset w_n$ be the set of all words formed in this way. Now a word in $w_{n-1}$ either ends in $00$ or $01$. If it ends in $00$ we can extend it to a word in $w_n$ by appending a $1$ to it, and if it ends in $01$ we can extend it to a word in $w_n$ by appending a $0$ to it. Let $B\subset w_n$ be the set of all words formed in this way. Now each word in $A$ ends in $00$, but each word in $B$ ends in $10$ or $01$, meaning that $A\cap B=\emptyset$. As $A$ is in one to one correspondence with words in $w_{n-2}$ and $B$ is in one to one correspondence with words in $w_{n-1}$ we must then have $|w_{n}|\geq |w_{n-1}|+|w_{n-2}|$.

Now $w_1=1$ and $w_2=2$, so the above proven claim means that $|w_n|\geq F_n$ (if we consider the Fibonacci sequence where $F_1=1$ and $F_2=2$). As $w_n$ is defined to be a subset of $W_n(X)$ we know $|W_n(X)|\geq|w_n|$. Transitivity of inequality gives that $|W_n(X)|\geq F_n$ for each $n\in \mathbb N$. Using this, along with the fact that $$h(\sigma_X)=\lim_{n\to \infty}\frac{1}{n}\log|W_n(X)|\quad\text{and}\quad F_n=\frac{\varphi^n-\psi^n}{\sqrt 5},$$ where $\psi:=\frac{1-\sqrt5}{2}$ allows us to prove that $h(\sigma|_X)\geq \log \varphi$.