RO-TST 2014 Problem 9

Let $f$ be the function of the set of positive integers into itself, defined by $f(1) = 1$ , $f(2n) = f(n)$ and $f(2n + 1) = f(n) + f(n + 1)$ . Show that, for any positive integer $n$ , the number of positive odd integers m such that $f(m) = n$ is equal to the number of positive integersless or equal to $n$ and coprime to $n$ .

[mod: the initial statement said less than $n$ , which is wrong.]