Results 1 to 2 of 2

Math Help - Counting problem

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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*}
    Last edited by SlipEternal; November 15th 2013 at 06:41 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: October 3rd 2012, 02:41 PM
  2. Another counting problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 19th 2011, 08:11 AM
  3. A counting problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 19th 2011, 05:19 AM
  4. Replies: 3
    Last Post: April 13th 2009, 06:42 PM
  5. a counting problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 01:40 PM

Search Tags


/mathhelpforum @mathhelpforum