Ox-words are sequences of letters $a$ and $b$ that are constructed according to the following rules: I. The sequence consisting of no letters is an Ox-word. II. If the sequence $W$ is an Ox-word, then the sequence that begins with $a$, followed by $W$ and ending in $b$, written $a W b$, is an Ox-word. III. If the sequences $U$ and $V$ are Ox-words, then the sequence $U$ followed by $V$, written $U V$, is an Ox-word. All Ox-words are constructed using these rules. The length of an Ox-word is the number of letters that occur in it. For example $a a b b$ and $a b a b$ are Ox-words of length 4. (i) Show that every Ox -word has an even length. (ii) List all Ox-words of length 6 . (iii) Let $W$ be an Ox-word. Is the number of occurrences of $a$ in $W$ necessarily equal to the number of occurrences of $b$ in $W$ ? Justify your answer. You may now assume that every Ox-word (of positive length) can be written uniquely in the form $a W b W ^ { \prime }$ where $W$ and $W ^ { \prime }$ are Ox-words. (iv) For $n \geqslant 0$, let $C _ { n }$ be the number of Ox-words of length $2 n$. Find an expression for $C _ { n + 1 }$ in terms of $C _ { 0 } , C _ { 1 } , \cdots , C _ { n }$. Explain your reasoning.
(i) [3 marks] The empty word has zero length which is even. If a new word is formed by Rule 2 then $a W b$ will have the same parity of length as $W$ had. Also if $U$ and $V$ are even-length words then so will be $U V$. So new words formed from words of even length will themselves be even. [0pt]
\section*{7. For APPLICANTS IN COMPUTER SCIENCE ONLY.}
Ox-words are sequences of letters $a$ and $b$ that are constructed according to the following rules:\\
I. The sequence consisting of no letters is an Ox-word.\\
II. If the sequence $W$ is an Ox-word, then the sequence that begins with $a$, followed by $W$ and ending in $b$, written $a W b$, is an Ox-word.\\
III. If the sequences $U$ and $V$ are Ox-words, then the sequence $U$ followed by $V$, written $U V$, is an Ox-word.
All Ox-words are constructed using these rules. The length of an Ox-word is the number of letters that occur in it. For example $a a b b$ and $a b a b$ are Ox-words of length 4.\\
(i) Show that every Ox -word has an even length.\\
(ii) List all Ox-words of length 6 .\\
(iii) Let $W$ be an Ox-word. Is the number of occurrences of $a$ in $W$ necessarily equal to the number of occurrences of $b$ in $W$ ? Justify your answer.
You may now assume that every Ox-word (of positive length) can be written uniquely in the form $a W b W ^ { \prime }$ where $W$ and $W ^ { \prime }$ are Ox-words.\\
(iv) For $n \geqslant 0$, let $C _ { n }$ be the number of Ox-words of length $2 n$. Find an expression for $C _ { n + 1 }$ in terms of $C _ { 0 } , C _ { 1 } , \cdots , C _ { n }$. Explain your reasoning.