I'd appreciate help in understanding how to approach/find a recurrence relation. For example, if we are given the following situation, how would one find a recurrence relation?
A computer system considers a string of decimal digits a valid codeword if it contains an even number of 0 digits. For instance, 1230407869 is valid, whereas 120987045608 is not valid. Let an be the number of valid n-digit codewords. Find a recurrence relation for an.
Thanks.
Best Answer
Let $a_n$ be as defined, and let $b_n$ be the number of strings of length $n$ with an odd number of $0$'s.
Then $$a_{n+1}=9a_n+b_n,$$ and $$b_{n+1}=a_n+9b_n.$$ To justify the first equation, note that we can obtain a legitimate codeword of length $n+1$ in two ways: (i) append any of the $9$ non-zero digits to a codeword of length $n$ or (ii) append a $0$ to a word of length $n$ that has an odd number of $0$'s.
We can turn the first recurrence into one that involves only $a_n$ by noting that $b_n=10^n-a_n$.
Remark: We can also turn the recurrences above into a second-order linear recurrence with constant coefficients.
In case you are interested, from the first equation we get $$a_{n+2}=9a_{n+1}+b_{n+1}.$$ Using the second equation, substituting for $b_{n+1}$, we get $$a_{n+2}=9a_{n+1}+a_n+9b_n.$$ But from the original first equation we have $b_n=a_{n+1}-9a_n$. Thus $$a_{n+2}=9a_{n+1}+a_n +9(a_{n+1}-9a_n).$$ This simplifies to $$a_{n+2}=18a_{n+1}-80a_n.$$
In this kind of problem, a single recurrence is often not the most useful thing. The two recurrences that we started with can be put in matrix form, and that matrix form can be very useful.