# Show that the sum of the largest odd divisors of n+1, n+2, …, 2n (where n is a natural number) is a perfect square?

I've been given the solution but I don't understand it at all, could someone please explain?

-
I don't think the algebraic-number-theory tag is applicable. –  andybenji Dec 30 '12 at 15:16
Have you tried breaking it down one statement at a time? For this particular problem, have you taken each statement and tried a numerical example as a means of following the statements? What have you tried? –  Amzoti Dec 30 '12 at 15:16
@Amzoti I understand what it says, I just don't understand how it proves that the sum is a perfect square... For example, what relevance does the statement about the 'odd part' of N have? –  Mathlete Dec 30 '12 at 15:17
The only slightly difficult thing about the quoted proof is that it switches from saying "largest odd divisor" to "odd part" about the same concept between the claim and its proof. –  Henning Makholm Dec 30 '12 at 15:19
@Mathlete: It's not really "the" pigeonhole principle, but a cousin. The usual pigeonhole principle says that if you have more pigeons than holes, at least one hole must hold more than one pigeon. But what we use here is that if you have exactly as many pigeons as you have holes, and there is no hole with more than one pigeon in it, then every hole must contain precisely one pigeon. –  Henning Makholm Dec 30 '12 at 15:27

The first thing to understand is that every positive integer $N$ can be written uniquely in the form $2^ab$, where $a$ is a non-negative integer, and $b$ is a positive odd integer. For example, $12=2^2\cdot3$ ($a=2,b=3$), $11=2^0\cdot 11$ ($a=0,b=11$), and $8=2^3\cdot1$ ($a=3,b=1$). In this decomposition the number $b$ is called the odd part of $N$, so $3$ is the odd part of $12$, $11$ is the odd part of $11$, and $1$ is the odd part of $8$. Note that the odd part of $N$ is indeed the largest odd number that divides $N$.

Next, notice that if $N$ and $M$ have the same odd part, then one of $N$ and $M$ is a multiple of the other. Say that $N=2^ab$ and $M=2^cb$, where $b$ is the odd part of $N$ and $M$; then either $a\le c$, in which case $M$ is a multiple of $N$, or $c\le a$, in which case $N$ is a multiple of $N$.

Now look at the integers $n+1,n+2,\dots,2n$. The largest of these, $2n$, is too small to be a multiple of the smallest, $n+1$, so none of these integers can be a multiple of another. Thus, they must all have different odd parts. The odd part of any integer is at most as large as that integer, so the largest possible odd part of any of the integers $n+1,\dots,2n$ is $2n$ $-$ except that $2n$ isn’t odd, so the largest possible odd part here is actually only $2n-1$.

There are $n$ numbers in the set $\{n+1,n+2,\dots,2n\}$, and each has a different odd part that is at most $2n-1$. The first $n$ odd positive integers are $1,3,\dots,2n-1$. Thus, the odd parts of the integers $n+1,n+2,\dots,2n$ must be precisely these $n$ odd integers, $1,3,\dots,2n-1$. Thus,

\begin{align*} \sum(\text{largest odd divisors of }n+1,n+2,\dots,2n)&=\sum(\text{odd parts of }n+1,n+2,\dots,2n)\\ &=1+3+\ldots+(2n-1)\;, \end{align*}

the sum of the first $n$ positive odd integers.

The proof by induction that $$1+3+\ldots+(2n-1)=n^2$$ is quite straightforward and can be found in many places.

-
We have a bijection between the set of odd numbers from $1$ to $2N-1$, and the set of numbers from $N+1$ to $2N$. The descriptive procedure, is to multiply by 2 till just before you go over $2N$, and to reverse it, you divide by $2$ as many times as you can.
As such, this shows that there is a bijection between the largest odd divisors of $N+1, N+2, \ldots, 2N$, and the set of odd numbers $1, 3, \ldots, 2N-1$, since multiplying / dividing by 2 doesn't affect the largest odd divisor.
Hence, the sum is $1 + 3 + \ldots + 2N-1 = N^2$.