Q: For each positive integer $n$, let $a_n$ denote the number of $n$-digit integers formed by the five numbers $1, 2, 3, 4 $and $5$ which do not contain consecutive $3’s$. Find a recurrence relation for $a_n$ with the necessary initial conditions. Also, find $a_n$ in terms of $n$ for each $n$.
I thought of using the method of solving for the characteristic roots for this question but I am clueless as to how I can proceed. Am I heading in the right direction? Some help will be deeply appreciated.
We have $a_0 = 1$, and $a_1 = 5$. Then, for $n \in \mathbb N$, we have $$ a_{n+2} = 4(a_{n+1} + a_n). $$ Namely, a string counted by $a_{n+2}$ is uniquely of one of two forms: a digit in $\{1,2,4,5\}$ followed by a string counted by $a_{n+1}$; or a $3$, followed by a digit in $\{1,2,4,5\}$, followed by a string counted by $a_n$.