5. (7-8 grade) Maria Ivanovna is a strict algebra teacher. She only puts twos, threes, and fours in the grade book, and she never gives the same student two twos in a row. It is known that she gave Vovochka 6 grades for the quarter. In how many different ways could she have done this? Answer: 448 ways.
Solution. Let $a_{n}$ be the number of ways to assign $n$ grades. It is easy to notice that $a_{1}=3$, $a_{2}=8$. Note that 3 or 4 can be placed after any grade, while 2 can only be placed if a 3 or 4 preceded it. Thus, a sequence of length $n$ can be obtained by appending 3 or 4 to a sequence of length $n-1$ or by appending 32 or 42 to a sequence of length $n-2$, from which we get the recurrence relation $a_{n}=2 a_{n-1}+2 a_{n-2}$. From this, it is easy to find that $a_{3}=22, a_{4}=60, a_{5}=164, a_{6}=448$.