Recurrence relation of Sn that depends on Sn-1

Question

OK, so I have run into this weird question about recurrence relations that I cannot complete by myself (first year comp. sci. student and first discrete math class, studying by myself). To help you better understand the question, I have written some examples right next to them (eg.). Here it is:

A password is valid if it contains an odd number of the digit 9 (eg. 1239499786 is valid but 129789945698 is not). Lets say that $S_n$ is the number of valid passwords that have $n$ digits. I need to find a recurrence relation for $S_n$. In other words, $S_n$ need to depend on $S_{\text{n - 1}}$.

Now I am not too good at this type of math and combinatorics are the worst for me. I have spent some time on this question, but I cannot see the answer, so please try to be a bit precise in your answers. I am sure that I will understand it if someone can provide a good explanation. Thanks, your help will be very appreciated!!! :D

Answer 1

I assume your passwords can have leading $0$'s, and you are dealing with decimal digits. If so, then with $S_n$ being the number of valid passwords with $n$ digits, have $n \ge 2$ and consider the left-most digit, say $d$. If $d$ is $9$, then for the password to be valid, the remaining digits must have an even number of digits, i.e., not be valid. There are $10^{n-1} - S_{n-1}$ such numbers. If $d$ is any other digit than $9$ (i.e., one of the other $9$ decimal digits), then the number would be valid if and only if the remaining $n-1$ digits have an odd number of the digit $9$, i.e., they are of the $S_{n-1}$ such valid passwords. Putting this together gives

$$S_n = (1)(10^{n-1} - S_{n-1}) + (9)(S_{n-1}) = 8S_{n-1} + 10^{n-1} \tag{1}\label{eq1A}$$

Of course, the starting point is $S_1 = 1$ since the only valid password with $1$ digit is $9$.