# 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

## 2 Answers

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