Songs of the Martian classical period had just two notes (let us call them $x$ and $y$ ) and were constructed according to rigorous rules: I. the sequence consisting of no notes was deemed to be a song (perhaps the most pleasant); II. a sequence starting with $x$, followed by two repetitions of an existing song and ending with $y$ was also a song; III. the sequence of notes obtained by interchanging $x$ s and $y$ s in a song was also a song. All songs were constructed using those rules. (i) Write down four songs of length six (that is, songs with exactly six notes). (ii) Show that if there are $k$ songs of length $m$ then there are $2 k$ songs of length $2 m + 2$. Deduce that for each natural number there are $2 ^ { n }$ songs of length $2 ^ { n + 1 } - 2$. Songs of the Martian later period were constructed using also the rule: IV. if a song ended in $y$ then the sequence of notes obtained by omitting that $y$ was also a song. (iii) What lengths do songs of the later period have? That is, for which natural numbers $n$ is there a song with exactly $n$ notes? Justify your answer.
\section*{5. For ALL APPLICANTS.}
Songs of the Martian classical period had just two notes (let us call them $x$ and $y$ ) and were constructed according to rigorous rules:\\
I. the sequence consisting of no notes was deemed to be a song (perhaps the most pleasant);\\
II. a sequence starting with $x$, followed by two repetitions of an existing song and ending with $y$ was also a song;\\
III. the sequence of notes obtained by interchanging $x$ s and $y$ s in a song was also a song.
All songs were constructed using those rules.\\
(i) Write down four songs of length six (that is, songs with exactly six notes).\\
(ii) Show that if there are $k$ songs of length $m$ then there are $2 k$ songs of length $2 m + 2$. Deduce that for each natural number there are $2 ^ { n }$ songs of length $2 ^ { n + 1 } - 2$.
Songs of the Martian later period were constructed using also the rule:\\
IV. if a song ended in $y$ then the sequence of notes obtained by omitting that $y$ was also a song.\\
(iii) What lengths do songs of the later period have? That is, for which natural numbers $n$ is there a song with exactly $n$ notes? Justify your answer.