Maths Olympiad Prep

Library / /189 of 377

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:
Prove that
σ(1)1+σ(2)2+σ(3)3++σ(n)n2n \frac{\sigma(1)}{1}+\frac{\sigma(2)}{2}+\frac{\sigma(3)}{3}+\cdots+\frac{\sigma(n)}{n} \leq 2 n
for every positive integer nn.

Solution

Solution:
This is similar to the previous solution. If dd is a divisor of ii, then so is i/di/d, and (i/d)/i=1/d(i/d)/i = 1/d. Summing over all dd, we see that σ(i)/i\sigma(i)/i is the sum of the reciprocals of the divisors of ii, for each positive integer ii. So, summing over all ii from 11 to nn, we get the value 1/d1/d appearing n/d\lfloor n/d \rfloor times, once for each multiple of dd that is at most nn. In particular, the sum is
11n1+12n2+13n3++1nnn<n12+n22++nn2. \frac{1}{1}\left\lfloor\frac{n}{1}\right\rfloor+\frac{1}{2}\left\lfloor\frac{n}{2}\right\rfloor+\frac{1}{3}\left\lfloor\frac{n}{3}\right\rfloor+\cdots+\frac{1}{n}\left\lfloor\frac{n}{n}\right\rfloor < \frac{n}{1^{2}}+\frac{n}{2^{2}}+\cdots+\frac{n}{n^{2}}.
So now all we need is 1/12+1/22++1/n2<21/1^{2} + 1/2^{2} + \cdots + 1/n^{2} < 2. This can be obtained from the classic formula 1/12+1/22+=π2/61/1^{2} + 1/2^{2} + \cdots = \pi^{2}/6, or from the more elementary estimate
1/22+1/32++1/n2<1/(12)+1/(23)++1/((n1)n)=(1/11/2)+(1/21/3)++(1/(n1)1/n)=11/n<1. \begin{aligned} 1/2^{2} + 1/3^{2} + \cdots + 1/n^{2} &< 1/(1 \cdot 2) + 1/(2 \cdot 3) + \cdots + 1/((n-1) \cdot n) \\ &= (1/1 - 1/2) + (1/2 - 1/3) + \cdots + (1/(n-1) - 1/n) \\ &= 1 - 1/n \\ &< 1. \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.