Recurrence relation in a Permutation and Combination Problem in Galois Theory by Ian Stewart

Question

The given problem is:

Let $P(n)$ be the number of ways to arrange $n$ zeros and ones in a row, given that ones occur in groups of three or more. Show that $$P(n) = 2P(n-1)-P(n-2)+P(n-4)$$ and deduce that as $\displaystyle{\lim_{n \to \infty}}$ $\frac{P(n+1)} {P(n)} \rightarrow x$, where $x > 0$ is real and $x^4-2x^3+x^2-1 = 0.$

The very first statement of the problem is not clear, $n$ is the number of total zeros and ones combined or there are $n$ zeros and few ones? Moreover, an arrangement having only zeros such as $000$ or $00000$ is acceptable or not is also doubtful.

I do not know how to approach this kind of problems, any reference book will be also very helpful.

Answer 1

I can tell from a general familiarity with these types of problems that $n$ refers to the combined number of $0$'s and $1$'s. If they omitted the restriction that $1$s occur in groups of three or more, there would be $2^n$ arrangements. However, you should double check this with whoever gave you the problem.

Also, the all zeroes sequence should be acceptable. You only have a problem if there exists a block of ones with size one or two; since there are no ones, there is no problem.

---

First I will "prove" that $P(n)=2P(n-1)$, then quantify the mistakes in that proof.

A sequence of length $n$ is specified by choosing the first $n-1$ numbers in $P(n-1)$ ways, then choosing the last number in two ways. Therefore, $P(n)=2P(n-1)$.

However, there are two problems:

• Suppose the sequence of length $n-1$ ended with a zero, and the last number was chosen to be one. Then the resulting sequence would end $01$, which is not valid. These "bad" sequences must be subtracted from the count of $2P(n-1)$. There are exactly $P(n-2)$ such "bad" sequences, since a bad sequence consists of a valid sequence of length $n-2$, followed by a $01$.

• Suppose the sequence of length $n$ ends with $0111$. Then there is not way to construct that sequence using the described method; the initial $n-1$ characters end with $011$, which is not valid, so is not accounted for by $P(n-1)$. These sequences ending with $0111$ are "missing" from the $2P(n-1)$ count, so they need to be added in to correct this. The number of "missing" sequences is $P(n-4)$.

Therefore, applying these corrections to the proof, you get $P(n)=2P(n-1)-P(n-2)+P(n-4)$. The conclusion about the limit of consecutive terms follows from the theory of solving homogeneous, linear recurrences with constant coefficients.