Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find the recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$'s or $2$'s.

The solution is $$ a_n = a_{n-1} + 2a_{n-2} + 2a_{n-3} + 2a_{n-4} + \dots. \tag1 $$

I've thought about this for quite some time and I can't really understand it. I feel like I'm making up my reasoning to fit the solution; rather than understanding why it really is in the above form.

Can someone please explain this combinatorially?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

As is common in problems of this type, it is useful to define other related sequences. Call a sequence with no two consecutive $1$'s or $2$'s good.

Let $p_n$ be the number of good sequences of length $n$ that end in $0$, $q_n$ the number that end in $1$, and $r_n$ the number that end in $2$.

We have the obvious recurrence $p_{n}=p_{n-1}+q_{n-1}+r_{n-1} =a_{n-1}$.

Also, $q_{n}=p_{n-1} +r_{n-1}$, and $r_{n}=p_{n-1}+q_{n-1}$. This is because, for example, to make a good sequence of length $n$ that ends in $1$, we take a good sequence of length $n-1$ that doesn't end in $1$, and append a $1$.

Add up. We get $a_{n}=2a_{n-1}+p_{n-1}$. But $p_{n-1}=a_{n-2}$. So we end up with the recurrence $$a_{n}=2a_{n-1}+a_{n-2}.$$ From this nice recurrence we can get a closed form. We can also get the recurrence of the post.

For assume by way of induction hypothesis that for a certain number $k$, we have $$a_k=a_{k-1}+2a_{k-2}+2a_{k-3}+\cdots$$ Then $$a_{k+1}=2a_k +a_{k-1}=a_k+(a_{k-1}+a_k)=a_k+(2a_{k-1}+2a_{k-2}+2a_{k-3}+\cdots).$$

share|improve this answer
    
When you did the induction hypothesis, did you obtain that from the solution or did you deduce that from the closed form? (Very helpful solution, ow!) –  AlanH Mar 26 '13 at 8:38
1  
Not from the closed form in terms of $(1\pm \sqrt{2})^n$, but from the short recurrence. –  André Nicolas Mar 26 '13 at 10:35
add comment

Take a good $n$-digit sequence, i.e., one with no $11$ or $22$ subsequence.

  • If it ends in $0$, the initial $(n-1)$-subsequence is good, so there are $a_{n-1}$ good $n$-sequences ending in $0$.

  • If it ends in $1$, it must actually end in either $01$ or $21$, and if it ends in $2$, it must actually end in either $02$ or $12$. A $0$ can follow any good sequence, so each good $(n-2)$-sequence gives rise to two good $n$-sequences, one ending in $1$ and one ending in $2$, by appending $01$ or $02$, respectively. Since there are $a_{n-2}$ good $(n-2)$-sequences, that accounts for the $2a_{n-2}$ good $n$-sequences ending in $01$ or $02$. That still leaves the $n$-sequences ending in $21$ or $12$ to be counted.

  • If the $n$-sequence ends in $21$, it must actually end in $021$ or $121$; similarly, if it ends in $12$, it must actually end in $012$ or $212$. The $021$ and $012$ cases can now be handled as before: a $0$ can follow any good sequence, so there are $a_{n-3}$ good $n$-sequences ending in $021$ and another $a_{n-3}$ ending in $012$; between them they account for another $2a_{n-3}$ good $n$-sequences, but the $n$-sequences ending in $121$ and $212$ remain to be accounted for.

The pattern should now be pretty clear. In fact we can do better. Suppose that the last $0$ in a given $n$-sequence is in the $k$-th position, where $k<n$. It can follow any of the $a_{k-1}$ good $(k-1)$-sequences, and it must be followed by either $1212\dots$ or $2121\dots$. Thus, for each $k<n$ there are $2a_{k-1}$ good $n$-sequences having their last $0$ in the $k$-th position.

share|improve this answer
add comment

Call the number of sequences that interest you that end in 0 $a_n$, if they end in 1 $b_n$, $c_n$ if they end in 2, and $d_n$ for ending in 3. Then clearly: $$ a_0 = b_0 = c_0 = d_0 = 1 $$ Now think how a sequence that ends in 0 can be built: Add a 0 to any of the others, so $a_{n + 1} = a_n + b_n + c_n + d_n$. To make a sequence ending in 1, anything except a sequence ending in 1 can come before, so it is $b_{n + 1} = a_n + c_n + d_n$. Continuing the same way: $$ \begin{align*} a_{n + 1} &= a_n + b_n + c_n + d_n \\ b_{n + 1} &= a_n + c_n + d_n \\ c_{n + 1} &= a_n + b_n + d_n \\ d_{n + 1} &= a_n + b_n + c_n + d_n \end{align*} $$ This setup serves for any restrictions you care to set up.

Now define generating functions: $$ \begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \\ B(z) &= \sum_{n \ge 0} b_n z^n \\ C(z) &= \sum_{n \ge 0} c_n z^n \\ D(z) &= \sum_{n \ge 0} d_n z^n \end{align*} $$ This gives the system of equations: $$ \begin{align*} \frac{A(z) - 1}{z} &= A(z) + B(z) + C(z) + D(z) \\ \frac{B(z) - 1}{z} &= A(z) + C(z) + D(z) \\ \frac{C(z) - 1}{z} &= A(z) + B(z) + D(z) \\ \frac{D(z) - 1}{z} &= A(z) + B(z) + C(z) + D(z) \end{align*} $$ By sheer luck, the values we are interested in are just the $a_{n + 1}$. Solving the system of equations we get: $$ A(z) = \frac{1 + z}{1 - 3 z - 2 z^2} $$ This can be split into (very ugly) partial fractions, and expand the resulting geometric series: $$ a_n = - \frac{\sqrt{17} - 1}{\sqrt{17} (\sqrt{17} + 3)} \cdot \left( - \frac{4}{\sqrt{17} + 3} \right)^n + \frac{\sqrt{17} + 1}{\sqrt{17} (\sqrt{17} - 3)} \cdot \left(\frac{4}{\sqrt{17} - 3} \right)^n $$ (this would need some more cleanup, sorry for the mess).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.