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.\ (a) Write down four songs of length 6 (that is, songs with exactly 6 notes).\ (b) 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 $n$ 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.\ (c) 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.