3
$\begingroup$

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

Solution

  • 0
    I don't think the algebraic-number-theory tag is applicable.2012-12-30
  • 0
    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?2012-12-30
  • 0
    @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?2012-12-30
  • 1
    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.2012-12-30
  • 0
    @HenningMakholm Oh that makes more sense; so the 'odd part' is the largest odd divisor. How does that relate to the proof though?2012-12-30
  • 0
    @Mathlete: Since the proof contains the explicit claim that you say you don't see how it proves: Where is the _first_ place in the proof it contains a statement that you don't think is justified?2012-12-30
  • 0
    @HenningMakholm Actually I understand it a lot better after your first comment - the part about N just threw me. I think it would've been better laid out if the sum of the odd numbers was mentioned at the end.2012-12-30
  • 0
    I think the issue is more of OP not understanding what "largest odd divisor means", and why the bijection exists.2012-12-30
  • 0
    Another thing I'm unsure of though is how this question/proof fits with the pigeonhole principle?2012-12-30
  • 0
    @Mathlete: You're right, the last sentence really ought to say "the sum of these" rather than just "this".2012-12-30
  • 1
    @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.2012-12-30
  • 0
    @HenningMakholm So in the context of this question, you're essentially saying that n+1,n+2,...,2n all have unique odd parts?2012-12-30
  • 0
    @Mathlete: Yes.2012-12-30
  • 0
    I completely understand it now, thanks for all your help!2012-12-30
  • 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$.