For any integer $n+1,\ldots, 2n$ ($n$ is a natural number) consider its greatest odd divisor. Prove that the sum of all these divisors equals $n^2.$
Problem
Source: ToT 2003-JO-3, SO-1
Tags: number theory proposed, number theory
18.06.2011 23:32
Consider the set $S = \{1,3,\ldots,2n-1\}$ of the $n$ odd positive integers between $1$ and $2n$. For each $k\in S$ there exists a unique $\alpha_k \geq 1$ such that $2^{\alpha_k}k > 2n$ but $2^{\alpha_k - 1}k \leq 2n$. Then $n < 2^{\alpha_k - 1}k \leq 2n$. All these numbers $2^{\alpha_k -1}k$ are clearly distinct, so they are exactly the numbers in the set $T = \{n+1,n+2,\ldots,2n\}$, since there are $n$ of them. Thus the largest odd divisors of the numbers in $T$ are precisely the numbers in $S$, and $\sum_{k\in S} k = \sum_{j=1}^n (2j-1) = n^2$.
02.01.2013 16:45
It's very easy using induction.. Let this statement is true for $n=k$. So, the sum of the greatest odd divisors of $k+1, k+2, k+3,.........., 2k$ is $k^2$. Now, when $n=k+1$ then the terms $2k+1$ and $2k+2$ are included and $k+1$ is excluded. Now $2k+1$ being a odd number the greatest odd divisor of it is itself. And the greatest odd divisor of $2k+2$ is same as that of $k+1$. So now the sum of the divisors become $k^2+2k+1$ which is $(k+1)^2$.
03.01.2013 19:57
suppose $g(m)$ denote the greatest odd divisor of $m$ we prove the result by induction. $P(n): g(n+1)+.....+g(2n)=n^2$ $P(1),P(2)$ are trivially true. I.H.- suppose $P(k)$ is true. so , $g(k+2)+.....+g(2k+2)$ $=[g(k+1)+........+g(2k)]+g(2k+1)+g(2k+2)-g(k+1)$ note that $g(2k+1)=2k+1 ,g(2(k+1))=g(k+1)$ so ,by IH, $g(k+2)+.....+g(2k+2)=k^2+2k+1=(k+1)^2$. so , $P(k+1)$ is true. so , by PMI , $P(n)$ is true for all $n\in N$