Finding a recurrence for the number of $n$-digit passwords having the same digit at least twice in a row

Question

Passwords consist of digits. A password is valid if it contains the same digit at least twice in a row. For example 4558, 000637 and 33972240 are valid passwords but 8385878 is not a valid password. Let $a_n$ denote the number of different valid passwords of length $n$.

I have been having trouble to figure out how to find a recurrence relation for this problem. I figured the password has to have at least two digits, so $a_2$ would be 10 possibilities(00,11,22,...,99)

Does anyone know if I am on the right track, and how to find the recurrence relation?

Answer 1

You're asking for a recurrence, and @YaniorWeg provided a nice answer. But the whole problem is much easier solved by counting the complement. I.e. How many strings have every pair of adjacent digits being different? I.e. How many strings have every digit (except the leftmost) being different from its left neighbor? Well, that's just $10 \times 9 \times 9 \times 9 \times ... = 10\times 9^{n-1}$.

Answer 2

Suppose $a_n$ is the number of words of length $n$ over the $m$-letter alphabet (in your case $m = 10$), that contain the same letter at least twice in a row. If a word contains the same letter at least twice in a row, then there are two mutually exclusive situations possible. The first one is, when the first encounter of the “double” letter is not on the end of your number. Then, if we erase the last letter, it will still satisfy such condition. Thus, the number of such words is $ma_{n-1}$. The other case is when the only “double” letters are the last two. The number of such words is $(m-1)(m^{n-2} - a_{n-2})$. The total number of such words is their sum $m^{n-2}(m-1) + ma_{n-1} - (m-1)a_{n-2}$.

Thus we have:

$$a_n = \begin{cases} 0 & \quad n \leq 1 \\ (m^{n-2} - a_{n-2})(m-1) + ma_{n-1} & \quad n \geq 2 \end{cases}$$