Largest odd factors summing to a square

Question

^{I just found this awesome puzzle from the Tournament of the Towns (though I'm sure it's appeared other places too). The connection between odd factors and square is surprising, and the proof has a lovely 'aha' moment. Enjoy!}

For any natural number $x$, prove that $$\sum_{y=x+1}^{2x}(\text{largest odd factor of y})=x^2.$$

Answer 1

Let $H(x) = (\text{largest odd factor of x})$. We can make two observations about this function:

1. $H(x) = H(\frac{x}{2})$, if x is even
2. $H(x) = x$, if x is odd

Let $$F(x) = \sum_{y=x+1}^{2x}H(x).$$

$F(1) = 1 = 1^2$. By induction, if $F(x) = x^2$, then

\begin{align*} F(x+1) &= F(x) + H(2x+2) + H(2x+1) - H(x+1) \\&= F(x) + H(x+1) + (2x+1) - H(x+1) \\&= F(x) + 2x+1 \\&= x^2 + 2x + 1 \\&= (x+1)^2 \end{align*}

Answer 2

ffao posted his answer while I was writing this up. I like my solution better, though in some sense it's equivalent to ffao's, so I'm posting mine too. I will of course be entirely unoffended if Rand gives the mighty green checkmark to ffao, who after all got there first.

It is well known that

the sum of all odd numbers below $2x$ is equal to $x^2$. And there are $x$ of these, from $2\cdot1-1$ to $2x-1$.

So presumably the sum we have here,

which has the right number of terms and consists entirely of odd numbers, will simply be a permutation of this.

Well,

take any odd number $t$ between $1$ and $2x$ inclusive. Keep doubling it until the next doubling would go beyond $2x$. You will end up with a number from $x+1$ to $2x$ inclusive, and clearly each such number appears just once. And the largest odd divisor of this number will be exactly $t$. We're done.

Or, to put it a bit more formally (possibly harder to follow quickly but easier to convince yourself it's definitely correct):

let $A=\{\,y\,:\,x+1\leq y\leq2x\,\}$ and $B=\{\,z\,:1\leq z\leq2x\,\&\,z \textrm{ odd}\,\}$;
define $f:A\rightarrow B$ and $g:B\rightarrow A$ by
$f(y)=\textrm{largest odd divisor of $y$}$ and
$g(z)=\textrm{largest $2^kz$ that's $\leq2x$}$;
then $f,g$ are inverses and therefore our sum, which is $\sum_{y\in A}f(y)$,
equals $\sum_{z\in B}z$, which famously equals $x^2$.