Largest odd factors summing to a square

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.$$

• I'm never around when the good math puzzles are posted :( – Quintec Feb 14 '18 at 1:00
• dude same :( aiyaaa – NL628 Feb 14 '18 at 4:42

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*}

• Whoa! Nice proof! What I had in mind was more like Gareth's proof, but this is really neat and fast. – Rand al'Thor Feb 14 '18 at 12:11

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$.

• Yes, in some sense this is actually equivalent to what I ended up doing. The good side to my solution is that there is no actual thinking required to reach it, but it ends up being less clean. – ffao Feb 14 '18 at 0:10
• You can also word it this way: Let: $x+1 = O_{x+1}*2^{E_{x+1}}$ ... $2x = O_{2x}*2^{E_{2x}}$ None of the numbers in the range can be a multiple of another, but if the $O$s of two numbers are identical, one of the numbers will be the multiple of other, so all $O$s must be different, which are the odd numbers up to $2x-1$. The sum will be $x^2$. – Nautilus Feb 14 '18 at 9:30
• "clearly each such number appears just once" - I think this could do with just a little more explanation, as it's really the crux of this proof. – Rand al'Thor Feb 14 '18 at 12:13
• This is the proof I had in mind when I posted the question (the 'aha' moment being what's in your first two spoilertags). But ffao's proof is so unexpectedly short and slick! I'm not sure where to put the checkmark now, but knowing me, it'll probably be a while until I award it anyway ;-) – Rand al'Thor Feb 14 '18 at 12:14
• One of the reasons for the more-formal spoilered paragraph was to be more explicit about that "clearly". (I claim it really is obvious that those functions f and g are inverses, and that's all you need.) – Gareth McCaughan Feb 14 '18 at 13:40