The following problem is given in Exercise 1.11 chapter 1 of "Galois Theory" by Ian Stewart. Let $P(n)$ be the number of binary strings of length $n$ in which consecutive ones occur in groups of three or more. Deduce that $\lim_{n\to +\infty}\frac{P(n+1)}{P(n)} = \ell > 0$ where $\ell$ is real and is a solution of the polynomial equation $x^4-2x^3+x^2-1 = 0$.
I managed to define recursively the set $A_n$ of binary strings of length $n$ in which consecutive ones occur in groups of three or more as follows
- $A_0 = \emptyset$
- $A_1 = \{0\}$
- $A_2 = \{00\}$
- $A_3 = \{000, 111\}$
- $A_4 = \{0000, 1111, 0111, 1110\}$
- if $n > 4$ and $x \in A_{n-1}$ then $0x \in A_n$
- if $n > 4$ and $x \in A_{n-4}$ then $1110x \in A_n$
- if $n > 4$ and $1x \in A_{n-1}$ then $11x \in A_n$
This explains why for $n > 4$ we have $P(n) = 2P(n-1) - P(n-2) + P(n-4)$.
Moreover i noticed that for $n > 4$ we have $P(n-2)-1 \leq P(n)-P(n-1) \leq P(n-2)+1$ so that $\frac{P(n-2)+P(n-1)-1}{P(n-1)} \leq \frac{P(n)}{P(n-1)} \leq \frac{P(n-2)+P(n-1)+1}{P(n-1)}$
Let $a_n = \frac{P(n-2)+P(n-1)-1}{P(n-1)}$ and $b_n = \frac{P(n-2)+P(n-1)+1}{P(n-1)}$. Then $a_n$ has a monotone increasing subsequence and $b_n$ has a monotone decreasing subsequence (how can I identify these?) so the convergence part is more or less ok.
But how on earth can i relate the limit $\ell$ to one of the roots of the polynomial ?