# Find recursive formula for number of sequences that meet criteria

I am given such a problem: Find the number $$a_n$$ of n-element ternary sequences (composed only of 0s, 1s and 2s), where:

a) There are no repetitions of 1 (two 1s cannot stand next to each other)

b) There are no repetitions of 1 and no repetitions of 2 (two 1s cannot stand next to each other, same for 2s)

I've managed to solve part a and got the following formula: $$a_n = a_n = 2\cdot a_{n-1} + 2\cdot a_{n-2}$$

However, when I attempt to solve part b, I cannot find a way to do it properly. I solved part a by assuming a 1-element sequence, and if the only element is 0 or 2 i can join any proper sequence of length $$n-1$$, else if the only element is 1, i can join either 0 or 2, and then join any proper sequence of length $$n - 2$$. Thanks for any help.

I’ll take you through my attack on the problem. As I’ll point out in places, it isn’t the most efficient, but it does illustrate a reasonable approach.

Let $$a_n$$ be the number of good strings of length $$n$$, $$b_n$$ the number of those that end in $$0$$, $$c_n$$ the number of them that end in $$1$$, and $$d_n$$ the number of them that end in $$2$$. Clearly $$a_n=b_n+c_n+d_n\;.$$

Since a $$0$$ can be appended to any good string to get another good string, we must have $$b_n=a_{n-1}$$. A $$1$$ can be appended to a good string that ends in $$0$$ or $$2$$ to get a good string, so $$c_n=b_{n-1}+d_{n-1}=a_{n-2}+d_{n-1}$$. Similarly, $$d_n=b_{n-1}+c_{n-1}=a_{n-2}+c_{n-1}\;.$$ Note that $$c_n+d_n=2a_{n-2}+c_{n-1}+d_{n-1}\;;$$ this suggests that we should combine the strings ending in $$1$$ and $$2$$ by defining $$e_n=c_n+d_n$$ and observing that $$e_n=2a_{n-2}+e_{n-1}$$. We now have only two variables, $$a_n$$ and $$e_n$$, with recurrences

$$a_n=b_n+e_n=a_{n-1}+2a_{n-2}+e_{n-1}\tag{1}$$

and

$$e_n=2a_{n-2}+e_{n-1}\;.\tag{2}$$

Here’s where we’ll do something a little tricky. We can rewrite $$(1)$$ as

$$e_{n-1}=a_n-a_{n-1}-2a_{n-2}$$

and shift the index down $$1$$ to get

$$e_{n-2}=a_{n-1}-a_{n-2}-2a_{n-3}\;.\tag{3}$$

Shifting the index down in $$(2)$$ yields $$e_{n-1}=2a_{n-3}+e_{n-2}$$, which we can combine with $$(3)$$ to express $$e_{n-1}$$ entirely in terms of $$a_k$$s with $$k:

$$e_{n-1}=2a_{n-3}+a_{n-1}-a_{n-2}-2a_{n-3}=a_{n-1}-a_{n-2}\;.$$

At this point we might realize that we could have got this much more directly: $$a_n=b_n+e_n$$, and $$b_n=a_{n-1}$$, so of course $$e_n=a_n-a_{n-1}$$ and hence $$e_{n-1}=a_{n-1}-a_{n-2}$$. Oh, well!

Now we can substitute this back into $$(1)$$ to get a recurrence for $$a$$:

$$a_n=a_{n-1}+2a_{n-2}+a_{n-1}-a_{n-2}=2a_{n-1}+a_{n-2}\;.$$

And this is so simple that it’s worth considering how we might have arrived at it directly. If we have a good string of length $$n-1$$ that ends in $$d$$, we can always append one of the two ternary digits different from $$d$$; that automatically gives us $$2a_{n-1}$$ good strings of length $$n$$. If $$d=0$$, we can also append a $$0$$. And how many good strings of length $$n-1$$ end in $$0$$? One for every good string of length $$n-2$$, since we could have appended a $$0$$ to any of them! Had we reasoned that way to begin with, we’d have arrived at the recurrence

$$a_n=2a_{n-1}+a_{n-2}$$

almost immediately.