1
$\begingroup$

In the notes of the following OEIS sequence( https://oeis.org/A006218), it is stated that $$\sigma_0(1) + \sigma_0(2) +... + \sigma_0(n) = \left[ \dfrac{n}{1} \right] + \left[ \dfrac{n}{2} \right] +... + \left[ \dfrac{n}{n} \right] , $$ where $\sigma_0(n)$ is the number of divisors of $n$, and $[x] $ denotes the integer part of $x$. How can one prove this identity? I tried approaching it inductively but i failed.

$\endgroup$
  • 1
    $\begingroup$ $$\sum_{k=1}^n \sigma(k) = \sum_{k=1}^n\sum_{d|k} d = \sum_{d=1}^n\sum_{k=1,d|k}^{n}d = \sum_{d=1}^n d\left\lfloor \frac {n} {d}\right\rfloor$$ $\endgroup$ – Dietrich Burde Jan 1 '18 at 20:09
2
$\begingroup$

We have $$\sum_{k=1}^n\sigma(k)=\sum_{k=1}^n\sum_{d\mid j}1=\sum_{d=1}^n \sum_{j:1\le j\le n,d\mid j}=\sum_{j=1}^n\left\lfloor\frac nj\right\rfloor.$$ In words, $\sum_{k=1}^n\sigma(k)$ counts the number of pairs $(j,k)$ of positive integers with $j\mid k$ and $k\le n$. In each such pair $1\le j\le n$, and the number of admissible $(j,k)$ for a given $j$ is the number of multiples of $j$ up to $n$, which is $\left\lfloor n/j\right\rfloor$.

$\endgroup$
  • $\begingroup$ This trick of switching the order of summation is very common and worth remembering; it can be used to prove lots of interesting identities. $\endgroup$ – Qiaochu Yuan Jan 1 '18 at 22:50
1
$\begingroup$

Hint: if you were to calculate the left-hand side by hand, how many times in total would $1$ be counted as a divisor of one of the numbers from $1$ to $n$? How many times would $2$ be counted as a divisor? What about $3$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.