Let $f$ be a function on nonnegative integers defined as follows $$f(2n) = f(f(n)) \quad \text{and} \quad f(2n+1) = f(2n)+1$$
(a) If $f(0) = 0$, find $f(n)$ for every $n$.
(b) Show that $f(0)$ cannot equal 1.
(c) For what nonnegative integers $k$ (if any) can $f(0)$ equal $2^{k}$?

For the rest of this problem, we assume that $\varphi$ is a non-degenerate symmetric bilinear form on $E$, and we denote by $q$ its quadratic form.
Let $F$ be a singular vector subspace of $E$. We assume that $(e_1, \ldots, e_s)$ is a basis of $F \cap F^\perp$. We denote by $G$ a supplementary subspace of $F \cap F^\perp$ in $F$.
a) Show that $G$ is non-singular.
b) Demonstrate by induction on the dimension of $F \cap F^\perp$ (starting with $\operatorname{dim}(F \cap F^\perp) = 1$, then $\operatorname{dim}(F \cap F^\perp) > 1$) that there exist $s$ planes $P_1, \ldots, P_s$ of $E$ such that the following three properties are verified:

1. For all $i \in \{1,\ldots,s\}$, $(P_i, q_{/P_i})$ is an artinian plane containing $e_i$.
2. For all $(i,j) \in \{1,\ldots,s\}^2$ with $i \neq j$, $P_i$ is orthogonal to $P_j$.
3. For all $i \in \{1,\ldots,s\}$, $P_i$ is orthogonal to $G$.

Let $n$ be a non-zero natural number. Show by induction $$\forall k \in \llbracket 0, 2^n - 1 \rrbracket, \quad k \in \operatorname{Im} \Phi_n$$ where $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.

Using the recurrence relation $2\beta_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \beta_k \beta_{n-k}$ and the analogous relation $2\alpha_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \alpha_k \alpha_{n-k}$ with $\alpha_0 = \beta_0 = 1$, deduce that $\beta_n = \alpha_n$ for every $n \in \mathbb{N}$.

Show that, for all $n \in \mathbb{N}$ and $\theta \in \mathbb{R}$, $T_n(\cos\theta) = \cos(n\theta)$.
The sequence of polynomials $\left(T_n\right)_{n \in \mathbb{N}}$ is defined by $T_0 = 1, T_1 = X$ and $\forall n \in \mathbb{N}, T_{n+2} = 2X T_{n+1} - T_n$.

Let $\mu_1$ and $\mu_2$ be two probabilities on $\mathbb{N}^*$. We assume that $\forall r \in \mathbb{N}^*, \mu_1(\mathbb{N}^* r) = \mu_2(\mathbb{N}^* r)$.
We recall that we denote by $(p_i)_{i \in \mathbb{N}^*}$ the sequence of prime numbers, ordered in increasing order.
Show that for all $r \in \mathbb{N}^*$ and all integer $n \geqslant 1$: $$\mu_1\left(\mathbb{N}^* r \backslash \bigcup_{i=1}^{n} \mathbb{N}^* r p_i\right) = \mu_2\left(\mathbb{N}^* r \backslash \bigcup_{i=1}^{n} \mathbb{N}^* r p_i\right).$$

Let $\mu_1$ and $\mu_2$ be two probabilities on $\mathbb{N}^*$. We suppose that $\forall r \in \mathbb{N}^*, \mu_1(\mathbb{N}^* r) = \mu_2(\mathbb{N}^* r)$, where $\mathbb{N}^* r$ denotes the set of strictly positive multiples of $r$. Using the result of 17a, show that for all $r \in \mathbb{N}^*$ and all integer $n \geqslant 1$: $$\mu_1\left(\mathbb{N}^* r \backslash \bigcup_{i=1}^{n} \mathbb{N}^* r p_i\right) = \mu_2\left(\mathbb{N}^* r \backslash \bigcup_{i=1}^{n} \mathbb{N}^* r p_i\right)$$

Let $c > 0$, and let $\left(a_n\right)_{n \in \mathbb{N}}$ be a sequence of positive real numbers such that $a_{n+1} \leq a_n - c(a_n)^2$ for all $n \in \mathbb{N}$. Show $a_n \leq a_0/(1 + nca_0)$ for all $n \in \mathbb{N}$. Hint: adapt the reasoning from question 10.c)

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.

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.

5. With an unlimited supply of black pebbles and white pebbles, there are 4 ways in which you can put two of them in a row: $B B , B W , W B$ and $W W$.
(a) Write down the 8 different ways in which you can put three of the pebbles in a row. In how many different ways can you put $N$ of the pebbles in a row?
Suppose now that you are not allowed to put black pebbles next to each other: with two pebbles there are now only 3 ways of putting them in a row, because $B B$ is forbidden.
(b) Write down the 5 different ways that are still allowed for three pebbles.
Now let $r _ { N }$ be the number of possible arrangements for $N$ pebbles in a row, still under the no-two-black-together restriction, so that $r _ { 2 } = 3$ and $r _ { 3 } = 5$.
(c) Show that for $N \geqslant 4$ we have $r _ { N } = r _ { N - 1 } + r _ { N - 2 }$. [Hint: Consider separately the two possible cases for the colour of the last pebble.]
Finally, suppose that we impose the further restriction that the first pebble and the last pebble cannot both be black. For $N$ pebbles call the number of such arrangements $w _ { N }$, so that for example $w _ { 3 } = 4$ (although $r _ { 3 } = 5$, the arrangement $B W B$ is now forbidden).
(d) When $N \geqslant 5$, write down a formula for $w _ { N }$ in terms of the numbers $r _ { i }$, and explain why it is correct.