how many sequences above 1,2,3,4,5,6,7 that don't contain odd couples

Question

I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above ${1,2,3,4,5,6,7}$ that don't contain odd couples of numbers (for example it can't contain 11 or 13 or 15 or 17 or 31 or 33 etc...)"

so what I did is the following:

• for a sequence beginning with 2 or 4 or 6 there's no limit so another $a_{n-1}$ options
• for a sequence beginning with 1 it can't get 1 or 3 or 5 or 7 afterwards. so let's look at the total number of legal options $a_{n-1}$ and subtract the legal sequences beginning with 1 or 3 or 5 or 7 = $4*a_{n-2}$. so in total we get $a_{n-1}-4*a_{n-2}$ options in total.
• the same goes for a sequence beginning with 3 or 5 or 7 as for a sequence beginning with 1 described above.

thus, if we sum all mentioned we get $a_n=7a_{n-1}-16a_{n-2}$. but I found that the correct answer would be $a_n=3a_{n-1}+12a_{n-2}$ from some reason. what am I doing wrong? would appreciate your advice,

Answer 1

Let $E_n$ denote the number of good sequences that end in an even number, $O_n$ the number that end in an odd number, and $a_n$ the total (so $a_n$ is the answer you seek).

We can always append an even number so $$E_{n}=3\times a_{n-1}$$ We can only append an odd number to a sequence that ends in an even number, so $$O_{n}=4\times E_{n-1}=12\times a_{n-2}$$ Thus $$a_n=E_n+O_n=3a_{n-1}+12a_{n-2}$$

Answer 2

It seems that you think there are $4a_{n-2}$ sequences of length $n-1$ that begin with an odd number. But that cannot be true because some of the $a_{n-2}$ sequences will themselves start with an odd number.

What I would do here would be to set up two sequences, with $b_n$ being the number of sequences of length $n$ that begin with an even number and $c_n$ counting sequences that begin with an odd number. Then we have $$ \begin{align} b_n &= 3(b_{n-1}+c_{n-1}) \\ c_n &= 4b_{n-1} \end{align} $$ And introducing $a_n=b_n+c_n$ this becomes $$ \begin{align} b_n &= 3a_{n-1} \\ a_n &= 4b_{n-1} + 3a_{n-1} \end{align} $$ Substitute in the expression for $b_n$ to get $$ a_n = 12a_{n-2} + 3a_{n-1} $$ I don't know why your "correct" answer has a different sign for the $12a_{n-2}$ term.