# Recurrence relation for string that doesn't contain 3 consecutive digits

A friend posed a problem to me from his textbook today in where one was asked to create a recurrence relation for the number of strings of length $n$ in which there are no 3 consecutive digits. We assume we are using 26 characters and 10 digits for 36 symbols total.

I have been trying to figure it out, but I can't quite seem to get there.

I get the impression I can check my results in the following way:

$36^n - 36^{n-3} \cdot 10^3$

As that would be all possible strings of length $n$ with all possibilities of 3 consecutive numbers removed. I am not sure if i can check my results in this way, nor really how to start on the relation. This is a first year university course, so I imagine the solution doesn't need to be too deep.

How can one start to solve this problem?

• No: $36^n-36^{n-3}10^3$ is not the correct answer. That counts the number of ways to get a string of $n$ letters that does not start with 3 digits. – Thomas Andrews Oct 29 '15 at 18:17
• How does one proceed then? – user184881 Oct 29 '15 at 18:29

Let $A_n$ be the number of such strings. Then:
$$A_{n+1}=26A_n + 10\cdot 26 A_{n-1} + 10^2\cdot 26A_{n-2}$$
The closed form is messy, since the roots of $x^3-26x^2-260x-2600$ are irrational and only one, $r\approx 35.415$, is real. The closed form will be dominated by $cr^n$ for some constant $c$.