I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns and coats. There exists one unique restriction: she cannot buy two big items in two weeks in a row. Write down a recursive sequence that represents the numbers of possible different purchases she can do in n weeks.
My idea: we have that $\;a_1= 6\;,\;\;a_2=2\cdot 6+4\cdot2=20\;$
Now, doing some cumbersome arithmetics, I reach $\;a_3=88\,$ , but I can't see what the recursion is.
If you can help me to understand thank you
Let $a_k$ be the number of allowed ("good") purchase sequences in $k$ weeks. Now look at $a_{n+1}$, the number of good purchase sequences in the first $n+1$ weeks.
The purchase in the $(n+1)$-th week can be of two types (i) Small or (ii) Big. We count the number of sequences each type.
For Type (i), we can append any small purchase to any good purchase sequence for the first $n$ weeks. Thus there are $2a_n$ good purchase sequences of length $n+1$ that end in a small purchase.
For Type (ii), the purchase sequence for the first $n$ weeks must have ended with a small. And the purchase sequence in the first $n-1$ weeks is unrestricted. Thus the number of Type (ii) sequences of length $n+1$ is $(4)(2)a_{n-1}$.
We have obtained the recurrence $a_{n+1}=2a_n+8a_{n-1}$.
Note that the basic idea is really the same as the one that you used to compute $a_3$.