Finding recurrence relation for digits

Question

codes have been generated odd number of odd digits. Let $ a_n $ be the number of valid n-digit activation codes. Find the recurrence relation.

I can't figure out and understand the question. Can you give me some hints ?

Answer 1

How can we generate a valid $n$-digit code? We can either

1. Take a valid $(n - 1)$-digit code and append an even digit to it. Since there are $5$ ways to choose an even digit, this can be done in $5 \cdot a_{n - 1}$ ways.
2. Take an invalid $(n - 1)$-digit code and append an odd digit to it. Observe that the number of invalid codes of length $n - 1$ is $10^{n - 1} - a_{n - 1}$. Since there are $5$ ways to choose an odd digit, this can be done in $5 \cdot (10^{n - 1} - a_{n - 1})$ ways.

In total, we get: $$ a_n = \underbrace{5 \cdot a_{n - 1}}_{\text{case 1}} + \underbrace{5 \cdot (10^{n - 1} - a_{n - 1})}_{\text{case 2}} = 5 \cdot 10^{n - 1} $$