1. ## Counting problem

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

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

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

A colleague told me that he thinks it should have some sort of a connection to $\displaystyle H_n$ (the n-th harmonic number) and the limit $\displaystyle \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 $\displaystyle F_n$, not $\displaystyle H_n$. Everything is clear now. And the formula I found for $\displaystyle 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 $\displaystyle n$ that do not contain the pattern 001. If the first digit is 1, then any binary sequence of length $\displaystyle n-1$ not containing the pattern 001 that follows will form a valid sequence of length $\displaystyle n$. There are $\displaystyle A_{n-1}$ of those.

If the first digit is zero and the second digit is 1, then any valid binary sequence of length $\displaystyle n-2$ that follows will form a valid binary sequence of length $\displaystyle n$. There are $\displaystyle 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 $\displaystyle n$ all of whose digits are zero.

So, the recursive formula is $\displaystyle A_n = A_{n-1} + A_{n-2} + 1, n\ge 2$. Since $\displaystyle 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 $\displaystyle A_n = 2A_{n-1} - A_{n-3}, n\ge 3$.

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

$\displaystyle 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:

\displaystyle \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, $\displaystyle c_1 = -1, c_2 = \dfrac{5+2\sqrt{5}}{5}, c_3 = \dfrac{5-2\sqrt{5}}{5}$. Hence,

\displaystyle \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 $\displaystyle \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,

\displaystyle \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 $\displaystyle |\phi| \approx 1.618>1, \left| \overline{\phi} \right| \approx 0.618<1$, so as $\displaystyle n \to \infty$, $\displaystyle \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:

\displaystyle \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 $\displaystyle n \to \infty, \left( \dfrac{ \overline{ \phi } }{ \phi } \right)^n \to 0$ since
\displaystyle \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*}