\section*{7. For APPLICANTS IN COMPUTER SCIENCE ONLY.}
In a game of Cat and Mouse, a cat starts at position 0 , a mouse starts at position $m$ and the mouse's hole is at position $h$. Here $m$ and $h$ are integers with $0 < m < h$. By way of example, a starting position is shown below where $m = 7$ and $h = 12$.\\
\includegraphics[max width=\textwidth, alt={}, center]{f229588a-5602-44a5-acb0-6efec65f41af-18_111_1068_550_493}

With each turn of the game, one of the mouse or cat (but not both) advances one position towards the hole on the condition that the cat is always strictly behind the mouse and never catches it. The game ends when the mouse reaches the safety of its hole at position $h$.

This question is about calculating the number, $g ( h , m )$, of different sequences of moves that make a game of Cat and Mouse.

Let $C$ denote a move of the cat and $M$ denote a move of the mouse. Then, for example, $g ( 3,1 ) = 2$ as $M M$ and $M C M$ are the only possible games. Also $C M C C M$ is not a valid game when $h = 4$ and $m = 2$ as the mouse would be caught on the fourth turn.\\
(i) Write down the five valid games when $h = 4$ and $m = 2$.\\
(ii) Explain why $g ( h , h - 1 ) = h - 1$ for $h \geqslant 2$.\\
(iii) Explain why $g ( h , 2 ) = g ( h , 1 )$ for $h \geqslant 3$.\\
(iv) By considering the possible first moves of a game, explain why

$$g ( h , m ) = g ( h , m + 1 ) + g ( h - 1 , m - 1 ) \quad \text { when } 1 < m < h - 1 .$$

(v) Below is a table with certain values of $g ( h , m )$ filled in. Complete the remainder of the table and verify that $g ( 6,1 ) = 42$.\\
\includegraphics[max width=\textwidth, alt={}, center]{f229588a-5602-44a5-acb0-6efec65f41af-18_778_787_1740_632}

End of Last Question