# Math Help - Counting problem

1. ## Counting problem

Let $A_n$ be the number of binary sequences of length $n$ that do not contain the pattern 001. Using Inclusion-Exclusion, I am pretty sure I found a pattern for $A_n$. I think it is

$A_n = \sum_{i\ge 0}(-1)^i\binom{n-2i}{i}2^{n-3i}$

Then, I want to find the following limit: $\lim_{n\to \infty} (A_n)^{1/n}$.

A colleague told me that he thinks it should have some sort of a connection to $H_n$ (the n-th harmonic number) and the limit $\lim_{n\to \infty} (H_n)^{1/n} = 1$. So far, I haven't been able to find any such connection.

2. ## Re: Counting problem

Never mind. My colleague meant $F_n$, not $H_n$. Everything is clear now. And the formula I found for $A_n$, while correct, is not the formula that helped me find the limit.

Instead, I needed a recursive formula. To find that, I count the number of binary sequences of length $n$ that do not contain the pattern 001. If the first digit is 1, then any binary sequence of length $n-1$ not containing the pattern 001 that follows will form a valid sequence of length $n$. There are $A_{n-1}$ of those.

If the first digit is zero and the second digit is 1, then any valid binary sequence of length $n-2$ that follows will form a valid binary sequence of length $n$. There are $A_{n-2}$ of those.

If the first two digits are zero, then the third digit cannot be 1 (or it would form the pattern 001). So, the third digit must be zero. By the same logic, every digit after must also be zero. There is only one binary sequence of length $n$ all of whose digits are zero.

So, the recursive formula is $A_n = A_{n-1} + A_{n-2} + 1, n\ge 2$. Since $A_n - A_{n-1} = (A_{n-1} + A_{n-2} + 1) - (A_{n-2} + A_{n-3} + 1) = A_{n-1} - A_{n-3}$, we also have $A_n = 2A_{n-1} - A_{n-3}, n\ge 3$.

This recursive relation has characteristic polynomial $x^3-2x^2+1 = (x-1)(x^2-x-1)$ which has roots $1, \dfrac{1+\sqrt{5}}{2}, \dfrac{1-\sqrt{5}}{2}$. So an explicit formula is:

$A_n = c_1(1)^n + c_2\left( \dfrac{ 1+\sqrt{5} }{2} \right)^n + c_3 \left( \dfrac{ 1 - \sqrt{5} }{2} \right)^n$.

There is one empty binary sequence, two binary sequences of length one, and four binary sequences of length two. Obviously, none of them contain the pattern 001.

This gives the system of equations:

\begin{align*}A_0 = 1 & = c_1 + c_2 + c_3 \\ A_1 = 2 & = c_1 + c_2 \dfrac{ 1+\sqrt{5} }{2} + c_3 \dfrac{ 1-\sqrt{5} }{2} \\ A_2 = 4 & = c_1 + c_2 \left( \dfrac{ 1 + \sqrt{5} }{2} \right)^2 + c_3 \left( \dfrac{ 1-\sqrt{5} }{2} \right)^2 \\ & = c_1 + c_2 \dfrac{ 3 + \sqrt{5} }{2} + c_3 \dfrac{ 3 - \sqrt{5} }{2}\end{align*}

Solving this system, $c_1 = -1, c_2 = \dfrac{5+2\sqrt{5}}{5}, c_3 = \dfrac{5-2\sqrt{5}}{5}$. Hence,

\begin{align*}A_n & = \dfrac{5+2\sqrt{5}}{5}\left(\dfrac{1+\sqrt{5}}{2} \right)^n + \dfrac{5-2\sqrt{5}}{5}\left(\dfrac{1-\sqrt{5}}{2}\right)^n - 1 \\ & = a\phi^n + b\overline{\phi}^n - 1\end{align*}

Where $\phi = \dfrac{1+\sqrt{5}}{2}, \overline{\phi} = \dfrac{1-\sqrt{5}}{2}, a = \dfrac{5+2\sqrt{5} }{5}, b = \dfrac{5-2\sqrt{5}}{5}$

So,

\begin{align*}\lim_{n \to \infty} \left[ a \phi^n + b \overline{\phi}^n - 1 \right]^{1/n} & = \lim_{n\to \infty} \exp\left( \dfrac{ \ln \left( a \phi^n + b \overline{\phi}^n -1 \right) }{n} \right) \\ & = \exp \left( \lim_{n \to \infty} \dfrac{ \ln \left( a \phi^n + b \overline{\phi}^n -1 \right) }{n} \right) \end{align*}

Since $|\phi| \approx 1.618>1, \left| \overline{\phi} \right| \approx 0.618<1$, so as $n \to \infty$, $\phi^n \to \infty, \overline{\phi}^n \to 0$. This implies the numerator and denominator both approach infinity, so I can apply L'Hospital's Rule. The derivative of the denominator is one, so it will be ignored:

\begin{align*}\exp \left( \lim_{n \to \infty} \dfrac{ \ln \left( a \phi^n + b \overline{\phi}^n -1 \right) }{n} \right) & = \exp \left( \lim_{n \to \infty} \dfrac{ a \phi^n \ln \phi + b \overline{\phi}^n \ln \overline{\phi} }{ a \phi^n + b \overline{\phi}^n - 1} \cdot \dfrac{ \dfrac{1}{ \phi^n } }{ \dfrac{1}{ \phi^n } } \right) \\ & = \exp \left( \lim_{ n \to \infty } \dfrac{ a \ln \phi + b \left( \dfrac{ \overline{\phi} }{ \phi } \right)^n \ln \overline{\phi} }{ a + b \left( \dfrac{ \overline{\phi} }{\phi} \right)^n - \dfrac{1}{\phi^n} } \right) \\ & = \exp\left( \dfrac{ a \ln \phi }{ a } \right) \\ & = e^{\ln \phi} \\ & = \dfrac{ 1+\sqrt{5} }{2} \end{align*}

Note: As $n \to \infty, \left( \dfrac{ \overline{ \phi } }{ \phi } \right)^n \to 0$ since
\begin{align*}\left| \dfrac{ \overline{ \phi } }{ \phi } \right| = \left| \dfrac{ \left( \dfrac{ 1 - \sqrt{5} }{2} \right) }{ \left( \dfrac{ 1 + \sqrt{5} }{2} \right) } \right| = \left| \dfrac{ (1-\sqrt{5})^2 }{ -4} \right| = \left| \dfrac{3-\sqrt{5}}{ -2} \right| \approx 0.382 < 1\end{align*}