# How to Find Recurrence Relation?

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.

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.

This may not be the most elegant solution, but so the first case is pretty simple. Take the number of valid strings in the previous, $a_{n - 1}$, you can't add a $0$ because that would make the previously valid string invalid, so you can add any digit from 1-9 (i.e. 9 digits). So right away we know that $a_n > 9a_{n - 1}$.

But what about the previously invalid strings? If it was invalid, then there were an odd number of 0's and adding one more will make it valid. Now it depends on whether or not you consider zero 0's an even number of 0's. If so just take the compliment of the valid strings: $10^{n - 1} - a_{n - 1}$. This gives:

$$a_n = 9a_{n - 1} + 10^{n - 1} - a_{n - 1} = 8a_{n-1} + 10^{n - 1}$$

If you don't consider zero 0's as an even number, then you have to subtract off all of the previously invalid strings which also had no 0's (we cannot make it valid in this case by adding a 0 at the end). Well that's just $9^{n - 1}$. So then we would have:

$$a_n = 8a_{n - 1} + 10^{n - 1} - 9^{n - 1}$$

Call $a_n$ the number of codewords, $b_n$ the number of non-codewords. Then clearly $a_n + b_n = 10^n$.

On the other hand, adding a 0 makes a codeword out of a non-codeword, and viceversa; adding any other digit leaves things as they were: \begin{align} a_{n + 1} &= 9 a_n + b_n \\ b_{n + 1} &= a_n + 9 b_n \end{align} There is a codeword of length 0, so $a_0 = 1$, and no non-codewords of length 0, or $b_0 = 0$.

You can substitute $b_n = 10^n - a_n$ to get $a_{n + 1} = 8 a_n + 10^n$

You can use generating functions to solve this. Define $A(z) = \sum_{n \ge 0} a_n z^n$ and similarly $B(z)$; multiply both recurrences by $z^n$, sum over $n \ge 0$. Recognize: $$\sum_{n \ge 0} a_{n + 1} z^n = \frac{A(z) - a_0}{z}$$ and using the initial values gives: \begin{align} \frac{A(z) - 1}{z} &= 9 A(z) + B(z) \\ \frac{B(z)}{z} &= A(z) + 9 B(z) \end{align} We are interested just in $A(z)$: $$A(z) = \frac{1 - 9 z}{1 - 18 z + 80 z^2} = \frac{1}{2 (1 - 10 z)} + \frac{1}{2 (1 - 8 z)}$$ This is just two geometric series: $$a_n = \frac{10^n + 8^n}{2}$$