recurrence problem for number of words Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits
{0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the 
recurrence. The first few values of $w_n$ are calculated for you: 
$w_1 = 1$;  2
$w_2= 6$;  20 21 23 02 12 32
$w_3 = 28$;  200 201 203 210 211 213 230 231 233 222
020 021 023 002 012 032
120 121 123 102 112 132
320 321 323 302 312 332
 A: In this answer $a_n=w_n$.
Let $b_{n}$ denote likely the number of words of length $n$ with
an even number of twos.
Then $a_{n}+b_{n}=4^{n}$ and $a_{n+1}=3a_{n}+b_{n}=2a_{n}+4^{n}$.
In order to solve it write down some of them:
$a_{1}=1$
$a_{2}=2.1+4$
$a_{3}=2.2.1+2.4+4^{2}$
$a_{4}=2.2.2.1+2.2.4+2.4^{2}+4^{3}$
A pattern shows up:
$a_{n}=\sum_{k=1}^{n}2^{n-k}4^{k-1}=2^{n-1}\sum_{k=1}^{n}2^{k-1}=2^{n-1}\left(2^{n}-1\right)$
Finally prove by induction that this is correct.
A: Let $a_n$ be the number of $n$-sequences with an odd number of $2$'s. Call these good sequences. Then the number of bad $n$-sequences is $4^n-a_n$.
We now express $a_{n+1}$ in terms of $a_n$. An $(n+1)$-sequence is good if (i) the last term is $0$, $1$, or $3$ and the sequence obtained by removing the last term is good or (ii) the last term is $2$ and the sequence obtained by removing the last term is bad. Moreover, all good sequences of length $n+1$ can be obtained in this way. Thus
$$a_{n+1}=3a_n+(4^n-a_n)=2a_n+4^n.\tag{1}$$
Remark: Note that $a_{n+2}=2a_{n+1}+4^{n+1}$, so $4^{n+1}=a_{n+2}-2a_{n+1}$.
From $4^n=a_{n+1}-2a^n$ we obtain $4^{n+1}=4a_{n+1}-8a_n$. It follows that
$$a_{n+2}-2a_{n+1}=4a_{n+1}-8a_n,$$
from which we get
$$a_{n+2}=6a_{n+1}-8a_n.\tag{2}$$
One may (or may not) prefer this homogeneous recurrence with constant coefficients.  
Added: We can now solve Recurrence (1) or (2). For (2), I would use the characteristic polynomial $x^2-5x+8$. It has roots $2$ and $4$, so the general solution of Recurrence (2) is $A2^n+B4^n$. We can find $A$ and $B$ using the initial conditions. 
