Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would appreciate if somebody could help me with the following problem:

Q: How to proof ?

The number of positive divisors of $n$ is denoted by $d(n)$

$$\sum_{i=1}^n\left\lfloor\frac{n}i\right\rfloor=\sum_{k=1}^nd(k)$$

share|improve this question

2 Answers 2

up vote 3 down vote accepted

This is basically just interchanging the order of the sums.

$$\sum_{k=1}^n d(k) = \sum_{k\le n} \sum_{d\mid k} 1 = \sum_{\substack{k\le n\\d\mid k}} 1 = \sum_{qd\le n} 1 = \sum_{d\le n} \sum_{q\le \frac nd} 1 =\sum_{d\le n} \left\lfloor \frac nd \right\rfloor= \sum_{d=1}^n \left\lfloor \frac nd \right\rfloor$$

All summations are only taken through integer indices.

I leave to you to check in detail whether $\{(k,d); k,d\in\mathbb N, k\le n, d\mid k, \}=\{(qd,d); q,d\in\mathbb N, qd\le n\}=\{(dq,d); q,d\in\mathbb N, q\le\frac nd\}$, which is the reason why there are only different expressions of the same sum.

share|improve this answer
    
Maybe I could also mention that you will see arguments of this type quite frequently if you read Apostol's Introduction to Analytic Number Theory. (And probably in many other books from that area.) –  Martin Sleziak Mar 22 at 11:32

Proof by induction. If $n=1$, $1=d(1)$ True.

Assume for $n=q$,

Then $$\sum_{i=1}^q\left\lfloor\frac{q}i\right\rfloor=\sum_{k=1}^qd(k)$$

Add $d(q+1)$ to both sides we have $$\lfloor\frac{q}{1} \rfloor+ \lfloor\frac{q}{2} \rfloor + \cdots + \lfloor\frac{q}{q} \rfloor + d(q+1)=\sum_{k=1}^{q+1}d(k)$$

But the number of divisors of $q+1$ -1 is the number of times the floor functions increase by 1. Therefore by induction it holds.

share|improve this answer
    
If I understand you correctly, by the last line of your post you mean that $\left\lfloor\frac{q+1}k\right\rfloor-\left\lfloor\frac{q}k\right\rfloor=1$ if and only if $k\mid q+1$. (And it is zero in all remaining cases.) –  Martin Sleziak Mar 22 at 10:41
    
Yes, i do thanks. –  John Marty Mar 23 at 0:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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