Greatest odd divisor function problem

Question

Show that where $f(n)$ denotes the greatest odd divisor of a positive integer $n$, $f(n+1)+f(n+2)+...+f(2n)=n^2$.

edit: This post has been solved:

Merely induct on n, and you will find that as f(2n+1)=2n+1, we get (n+1)^2=n^2+2n+1 which is clearly true for all n. See solution below.

Answer 1

Induction: $n = 1$ is easy; both sides are equal to $1$.

Suppose true for some $n > 0$. Now we prove for $n + 1$: $$f(n+2) + \dots + f(2n) + f(2n + 1) + f(2n + 2) = f(n+1) + f(n+2) + \dots + f(2n) + (2n+1).$$ Here I've used $f(2n+2) = f(2(n+1)) = f(n+1)$ and $f(2n+1) = 2n + 1$.

Now the RHS of the indented equation is, by inductive hypothesis, $n^2 + (2n + 1) = (n+1)^2$, as required.