0

Let $x_n$ be the number of words length n where the alphabet is made up of 1, 2, 3, 4 and there are always an odd number of 2's(for example, $x_1$ = 1 because there is only one word of length 1 with an odd number of 2's). Find a recurrence relation for $x_n$ = something.

How would I get it to be something like $x_n = x_{n-1} + x_{n-2}$. I solved for the first 3: $x_0 = 0$, $x_1 = 1$, and $x_2 = 6$, but I have no idea where to go from here.

Malingos
  • 5

1 Answers1

0

Let $x_n$ be as you defined it and $y_n$ be the number of words with an even number of $2$'s. Then, $x_n = y_{n-1}+3x_{n-1}$ since we either start with a $2$ or not. And similarly, $y_n = x_{n-1}+3y_{n-1}$.

You can use these to get a recurrence relation for $x_n$.

mathworker21
  • 34,399
  • OK how would I use the $y_{n-1}$ with generating functions or to solve for $c_1r_1^n+c_2r_2^n=a_n$? – Malingos Mar 24 '17 at 02:28