Problem 5. If $a_{0}=0$ and $a_{n}=a_{\left[\frac{n}{2}\right]}+\left[\frac{n}{2}\right], n \geq 1$, find $\lim _{n \rightarrow+\infty} \frac{a_{n}}{n}$.
5. We shall prove by induction on $n$ that $a_{n}=n-t_{2}(n)$, where $t_{2}(n)$ is the number of 1 's in the binary representation of $n$. For $n=0$ we have $a_{0}=0$ and the assertion is true. Let us assume that it is true for every $n \leq k-1$. If $k=2 k_{0}$, then $t_{2}\left(k_{0}\right)=t_{2}(k)$ (the binary representations of $k_{0}$ and $k=2 k_{0}$ have the same number of 1 's) and we obtain

$$
a_{k}=a_{k_{0}}+k_{0}=k_{0}-t_{2}\left(k_{0}\right)+k_{0}=k-t_{2}\left(k_{0}\right)=k-t_{2}(k)
$$

If $k=2 k_{0}+1$, then $t_{2}\left(2 k_{0}+1\right)=t_{2}\left(2 k_{0}\right)+1$ (the binary representation of $2 k_{0}+1$ has one more 1 than this of $2 k_{0}$ ) and we get

$$
\begin{aligned}
a_{k} & =a_{k_{0}}+k_{0}=k_{0}-t_{2}\left(k_{0}\right)+k_{0}=2 k_{0}-t_{2}\left(2 k_{0}\right) \\
& =2 k_{0}+1-t_{2}\left(2 k_{0}+1\right)=k-t_{2}(k)
\end{aligned}
$$

Since $n \geq 2^{t}-1$ for $t_{2}(n)=t$, we have

$$
0 \leq \lim _{n \rightarrow+\infty} \frac{t_{2}(n)}{n} \leq \lim _{t \rightarrow+\infty} \frac{t}{2^{t}}=0
$$

Hence $\lim _{n \rightarrow+\infty} \frac{t_{2}(n)}{n}=0$ and therefore

$$
\lim _{n \rightarrow+\infty} \frac{a_{n}}{n}=\lim _{n \rightarrow+\infty} \frac{n-t_{2}(n)}{n}=1-\lim _{n \rightarrow+\infty} \frac{t_{2}(n)}{n}=1
$$