3
$\begingroup$

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

Solution

  • 0
    @Mathlete Saying Pigeonhole / cousin is actually distracting. What we have is we have a __bijection__ between an odd number from $1$ to $2N$, and a number from $N+1$ to $2N$, where the bijection is multiply by 2 but do not go over.2012-12-30

2 Answers 2

5

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.

2

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