Exercise 1

A database uses record identifiers that are alphanumeric strings in which the $10$ decimal digits and $26$ upper-case letters are valid symbols. The criteria that define a valid record identifier are recursive. A valid record identifier of length $n\geq 2$ can be constructed in the following ways:

• beginning with any upper-case letter other than $D$ and followed by any valid record identifier of length $n-1$;
• beginning with $1C$, $2K$, or $7J$ and followed by any valid record identifier of length $n-2$; or
• beginning with $D$ and followed by any string of $n-1$ decimal digits.

Let $r(n)$ denote the number of valid record identifiers of length $n$. We take $r(0)=1$ and note that $r(1) = 26$. Find a recursion for $r(n)$ when $n\geq 2$ and use it to compute $r(5)$.