For any integer n+1,…,2n (n is a natural number) consider its greatest odd divisor. Prove that the sum of all these divisors equals n2.
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,…,2n−1} of the n odd positive integers between 1 and 2n. For each k∈S there exists a unique αk≥1 such that 2αkk>2n but 2αk−1k≤2n. Then n<2αk−1k≤2n. All these numbers 2αk−1k are clearly distinct, so they are exactly the numbers in the set T={n+1,n+2,…,2n}, since there are n of them. Thus the largest odd divisors of the numbers in T are precisely the numbers in S, and ∑k∈Sk=∑nj=1(2j−1)=n2.
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 k2. 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 k2+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)=n2 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)=k2+2k+1=(k+1)2. so , P(k+1) is true. so , by PMI , P(n) is true for all n∈N