# Recurrence relation for the number of strings of length $n$ over the alphabet $\{1, 2,3,4,5,6,7\}$ such that there are no consecutive $1$'s or $2$'s.

Find a recurrence relation for the number of strings of length $$n$$ over the alphabet $$\{1, 2,3,4,5,6,7\}$$ such that there are no consecutive $$1$$'s or $$2$$'s.

I have no idea where to start. I've been stuck for some time. Any help is appreciated, Thanks.

• How can there be consecutive $0$s if there are no $0$s. – fleablood Mar 13 '19 at 23:21
• oops, changed $0$'s to $2$'s – Adi Mar 13 '19 at 23:23

Make coupled recurrences, one for the number of good strings of length $$n$$ that do not end in $$1$$ or $$2$$ and one for the number of good strings that do end in $$1$$ or $$2$$. Given the number of each, how many strings of length $$n+1$$ of each type are there?

Building on Ross's hint.

Let $$a_n$$ be the number of good strings of length $$n$$

Let $$b_n$$ be the number of good strings of length $$n$$ which do not end in a $$1$$ or $$2$$

Let $$c_n$$ be the number of good strings of length $$n$$ which end in $$1$$

Let $$d_n$$ be the number of good strings of length $$n$$ which end in $$2$$

This gives the recurrence $$a_n=b_n+c_n+d_n$$

Obviously, $$b_n = 5a_{n-1}$$

Also we have $$c_n=b_{n-1}+d_{n-1}$$ because the right hand side of the equation is the number of good strings of length $$n-1$$ which do not end in a $$1$$.

Finally, $$d_n=b_{n-1}+c_{n-1}$$ because the right hand side of the equation is the number of good strings of length $$n-1$$ which do not end in a $$2$$

Substituting for $$b_n$$, $$c_n$$, $$d_n$$ in the first equation the equations we get, $$a_n = 5a_{n-1}+b_{n-1}+d_{n-1}+b_{n-1}+c_{n-1}$$ = $$5a_{n-1}+b_{n-1}+a_{n-1}$$ = $$6a_{n-1}+5a_{n-2}$$

Therefore, $$a_n=6a_{n-1}+5a_{n-2}$$

Strings of length $$n\ge 2$$ fall in two classes; those that end with a double letter, and those that do not. There are $$6a_{n-1}$$ strings which do not end with a double letter (six choices for the end letter, anything but the previous), and $$5a_{n-2}$$ which do (five choices for the double, anything but $$11$$ or $$22$$), so $$a_{n}=6a_{n-1}+5a_{n-2},\qquad n\ge2.$$

• Very neat but I think... while deleting $22$ does leave a legal string of length $n-1$, it doesn't leave all possible legal strings of length $n-1$, namely, it doesn't leave legal strings of length $n-1$ which end in $2$. A pity if I'm right though, as this is much neater than Ross's standard solution. – antkam Mar 14 '19 at 5:01
• antkam, while Ross's solution is very neat, i think you're right. – Adi Mar 14 '19 at 11:00
• @antkam Yep, I was way off! Oh well, with the hind sight of Adi's answer, I can now give a nice combinatorial proof of the recursion. – Mike Earnest Mar 14 '19 at 15:06
• Great! It often (always?) happens that a set of coupled recurrences can be reduced to only 1 recurrence of the main series. I've often wondered if the single recurrence can then be "retroactively" explained -- it's lovely that you found the way in this case. If you have "general techniques" to share, I'd love to hear them. :) – antkam Mar 14 '19 at 19:07
• @antkam No general techniques yet, though I certainly want to know them and thing they must exist. BTW, the answer to your "always?" question is yes. Any system of recurrences can be described by a vector-matrix recurrence ${\bf v}_{n+1}=A{\bf v}_n$. The characteristic polynomial of $A$ gives a univariate recurrence solved by each coordinate of ${\bf v}_n$, allowing you to decouple. – Mike Earnest Mar 14 '19 at 19:23