\section*{2. For ALL APPLICANTS.}
The functions $f ( n )$ and $g ( n )$ are defined for positive integers $n$ as follows:

$$f ( n ) = 2 n + 1 , \quad g ( n ) = 4 n$$

This question is about the set $S$ of positive integers that can be achieved by applying, in some order, a combination of $f _ { \mathrm { s } }$ and $g \mathrm {~s}$ to the number 1 . For example as

$$g f g ( 1 ) = g f ( 4 ) = g ( 9 ) = 36$$

and

$$f f g g ( 1 ) = f f g ( 4 ) = f f ( 16 ) = f ( 33 ) = 67$$

then both 36 and 67 are in $S$.\\
(i) Write out the binary expansion of 100 (one hundred).\\[0pt]
[Recall that binary is base 2. Every positive integer $n$ can be uniquely written as a sum of powers of 2, where a given power of 2 can appear no more than once. So, for example, $13 = 2 ^ { 3 } + 2 ^ { 2 } + 2 ^ { 0 }$ and the binary expansion of 13 is 1101 .]\\
(ii) Show that 100 is in $S$ by describing explicitly a combination of $f _ { \mathrm { S } }$ and $g$ s that achieves 100 .\\
(iii) Show that 200 is not in $S$.\\
(iv) Show that, if $n$ is in $S$, then there is only one combination of applying $f _ { \mathrm { s } }$ and $g$ s in order to achieve $n$. (So, for example, 67 can only be achieved by applying $g$ then $g$ then $f$ then $f$ in that order.)\\
(v) Let $u _ { k }$ be the number of elements $n$ of $S$ that lie in the range $2 ^ { k } \leqslant n < 2 ^ { k + 1 }$. Show that

$$u _ { k + 2 } = u _ { k + 1 } + u _ { k }$$

for $k \geqslant 0$.\\
(vi) Let $s _ { k }$ be the number of elements $n$ of $S$ that lie in the range $1 \leqslant n < 2 ^ { k + 1 }$. Show that

$$s _ { k + 2 } = s _ { k + 1 } + s _ { k } + 1$$

for $k \geqslant 0$.



This page has been intentionally left blank