HMMT 二月 2004 · 团队赛 · 第 15 题

英文解析

15. Prove thatσ (1) σ (2) σ (3) σ ( n ) + + + · · · + ≤ 2 n
    1 2 3 nfor every positive integer n .
    Solution: This is similar to the previous solution. If d is a divisor of i , then so is i/d ,
    and ( i/d ) /i = 1 /d . Summing over all d , we see that σ ( i ) /i is the sum of the reciprocalsof the divisors of i , for each positive integer i . So, summing over all i from 1 to n , weget the value 1 /d appearing b n/d c times, once for each multiple of d that is at most n .
    In particular, the sum is
    ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋
    1 n 1 n 1 n 1 n n n n + + + · · · + < + + · · · + .
    2 2 2
    1 1 2 2 3 3 n n 1 2 n
    2 2 2
    So now all we need is 1 / 1 + 1 / 2 + · · · + 1 /n < 2. This can be obtained from the
    2 2 2
    classic formula 1 / 1 + 1 / 2 + · · · = π / 6, or from the more elementary estimate
    ( )
    2 2 2
    1 / 2 + 1 / 3 + · · · + 1 /n < 1 / (1 · 2) + 1 / (2 · 3) + · · · + 1 / ( n − 1) · n
    ( ) = (1 / 1 − 1 / 2) + (1 / 2 − 1 / 3) + · · · + 1 / ( n − 1) − 1 /n = 1 − 1 /n < 1 .