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

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.

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.

• Thanks!!! i got the same result but in a more complicated approach!! Thank you so much i'll study it :D – smalldinosaur Oct 21 '14 at 20:17
• You are welcome. To get an explicit formula, one can use Recurrence 1 and "climb down." In a way that is nicer, in the sense of being more concrete, but it does take longer. – André Nicolas Oct 21 '14 at 21:01