Guys, I am having trouble finding recurrent relation.
A codeword is made up of the digits $0,1,2,3$ (order is important!). A codeword is defined as legitimate if and only if it has an even number of $0$’s. Let $a_n$ be the number of legitimate codewords of lenth $n$. Write a recurrence for $a_n$.
The answer is $a_n = 3a_{n-1} + 4^{n-1} - a_{n-1}$
I know where $a_n=3a_{n-1}$ came from, but the problem is, I can't figure out where the rests ($4^{n-1} - a_{n-1}$) came from!
Please can anyone tell me how to approach the question?
Thank you!
So lets look at a word $w = w_1 \ldots w_n$ of length $n$ with $w_i \in \{0,1,2,3\}$ and denote by $w' = w_2 \ldots w_n$ the word consisting of all but the first letter. $w$ is legimate in the following cases:
$w_1 \ne 0$ and $w'$ is legitimate (as then the number of $0$s in $w$ equals that in $w'$. There are 3 possiblities for $w_1$ and $a_{n-1}$ for $w'$, hence $3a_{n-1}$ for $w$ in this form.
$w_1 = 0$, and $w'$ is illegitimate (as then the number of $0$s in $w'$ has to be odd) there are $4^{n-1}$ wors of 4 letters with length $n-1$, of which $a_{n-1}$ are legitimate, hence $4^{n-1}-a_{n-1}$ illegitimate. So $4^{n-1}-a_{n-1}$ possibilities for $w$ in this case.