Amount of numbers divisible by 3

Question

Let $a_n$ be the amount of numbers consisting of $n$ digits from $\{1,2,3,4,5\}$ that are divisible by $3$ (giving an integer solution).

I'm asked to proof that the following recurrence relation holds for $a_n$: $$\begin{cases} a_n+a_{n-1}=2\cdot5^{n-1}\\a_1=1\end{cases}$$

I can't seem to find out how to start solving this problem, so can someone please give me a hint to where to start?

Answer 1

Consider all the possible $5^{n-1}$ numbers of length $n-1$ from the set.

Of these, $a_{n-1}$ are already divisible by three. Only by adding 3 can we get a valid number. Of the rest, adding two numbers (either 1 and 4 or 2 and 5) will result in a valid number. In all then, we get $$a_n=2\cdot(5^{n-1}-a_{n-1})+a_{n-1}$$ from which the recurrence follows.