\section*{7. For APPLICANTS IN COMPUTER SCIENCE ONLY.}
Consider sequences of the letters M, X and W. Valid sequences are made up according to the rule that an M and a W can never be adjacent in the sequence. So M, XMXW, and XMMXW are examples of valid sequences, whereas the sequences MW and XWMX are not valid.\\
(i) Clearly, there are 3 valid sequences of length 1 . List all valid sequences of length 2 .\\
(ii) Let $g ( n )$ denote the number of valid sequences of length $n$. Further, let $m ( n ) , x ( n )$, $w ( n )$ denote the number of valid sequences of length $n$ that start with an M , an X , a W respectively.

Explain why

$$\begin{aligned}
m ( n ) & = w ( n ) , \\
m ( n ) & = m ( n - 1 ) + x ( n - 1 ) \quad \text { for } n > 1 , \\
x ( n ) & = 2 m ( n - 1 ) + x ( n - 1 ) \quad \text { for } n > 1 ,
\end{aligned}$$

and write down a formula for $g ( n )$ in terms of $m ( n )$ and $x ( n )$.\\
Hence compute $g ( 3 )$, and verify that $g ( 4 ) = 41$.\\
(iii) Given a sequence using these letters then we say that it is reflexive if the following operation on the sequence does not change it: reverse the letters in the sequence, and then replace each occurrence of M by W and vice versa. So MXW, WXXM and XWXMX are reflexive strings, but MXM and XMXX are not. Let $r ( n )$ be the number of valid, reflexive sequences of length $n$.

If a sequence is reflexive and has odd length, what must the middle letter be? Explain your answer.

Hence, show that

$$r ( n ) = \left\{ \begin{array} { c l } 
x \left( \frac { n + 1 } { 2 } \right) & \text { if } n \text { is odd } \\
x \left( \frac { n } { 2 } \right) & \text { if } n \text { is even. }
\end{array} \right.$$