4
$\begingroup$

I am trying to prove the identity

$$t(1) + t(2) + \cdots + t(n) = \Big\lfloor \dfrac{n}{1} \Big\rfloor + \Big\lfloor \dfrac{n}{2} \Big\rfloor + \cdots + \Big\lfloor \dfrac{n}{n} \Big\rfloor,$$

where $t(j)$ is the number of divisors of $j$.

Attempt: The highest power of $k \in \{2, 3, \ldots, n\}$ that divides $n!$ is given by

$$H_{k} := \Big\lfloor \dfrac{n}{k}\Big\rfloor + \Big\lfloor \dfrac{n}{k^{2}}\Big\rfloor + \cdots + \Big\lfloor\dfrac{n}{k^{N_{c}}}\Big\rfloor,$$

where $N_{c}$ is the maximal integer satisfying $k^{N_{c}} \leq n$. With a little thought, one can see that

\begin{equation*} \begin{split} \Big\lfloor\dfrac{n}{1}\Big\rfloor + \Big\lfloor\dfrac{n}{2}\Big\rfloor + \cdots + \Big\lfloor\dfrac{n}{n}\Big\rfloor &= H_{2} + H_{3} + \cdots + H_{n} + \Big\lfloor\dfrac{n}{1}\Big\rfloor \\ &= H_{2} + H_{3} + \cdots + H_{n} + n. \end{split} \end{equation*}

Each $H_{k}$ is a counted in the sum $t(1) + t(2) + \cdots + t(n)$, since each $t(k^{j})$ is a summand for $j \in \{1, 2, \ldots, N_{k}\}$, and also each $t(m)$ is a summand, where $m$ is a multiple of $k$ less than or equal to $n$.

This is where I'm a little stuck: I think that the only other summand in $t(1) + t(2) + \cdots + t(n)$ would be $1 + 1 + \cdots + 1 = n$, since each $t(j)$ counts $1$ as a divisor. My problem is showing that these are the only extra terms in $t(1) + t(2) + \cdots + t(n)$, which would show equality.

Any hints would be appreciated, or even suggestions of going about it a different way.

$\endgroup$
1
$\begingroup$

For the sake of completeness I would like to point out that this is usually done by induction. We seek to show that

$$\sum_{k=1}^n \tau(k) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

It holds for $n=1:$ $$\tau(1) = \lfloor 1\rfloor.$$

In the induction step we start from

$$\sum_{k=1}^n \tau(k) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

to get

$$\tau(n+1) + \sum_{k=1}^n \tau(k) = \tau(n+1) + \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

Now $$\tau(n+1) = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right)$$

since

$$\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor = \begin{cases} 1 \quad\text{if}\quad k|n+1 \\ 0 \quad\text{otherwise}.\end{cases}$$

Therefore we have

$$\sum_{k=1}^{n+1} \tau(k) = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right) + \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor \\ = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right) + \sum_{k=1}^{n+1} \bigg\lfloor \frac{n}{k} \bigg\rfloor \\ = \sum_{k=1}^{n+1} \bigg\lfloor \frac{n+1}{k} \bigg\rfloor$$

and the induction is complete.

$\endgroup$
  • $\begingroup$ This is a much easier approach. Thank you. $\endgroup$ – Fred Apr 20 '16 at 0:57
  • $\begingroup$ Is this really usually done by induction? $\endgroup$ – Unit Apr 20 '16 at 23:07
3
$\begingroup$

It really helps to write $t(1)+t(2)+\dotsb+t(n)$ in a triangular array:

1 + 
1 + 1 +
1 + 0 + 1 +
1 + 1 + 0 + 1 +
1 + 0 + 0 + 0 + 1 +
1 + 1 + 1 + 0 + 0 + 1 +
1 + 0 + 0 + 0 + 0 + 0 + 1 +
1 + 1 + 0 + 1 + 0 + 0 + 0 + 1 + 
1 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 1 + ...

Row $k$ is $t(k)$ written in a way that indicates which numbers from 1 to $k$ divide $k$. What do you see vertically?

As a final hint, note that $\lfloor n/d \rfloor$ counts the number of multiples of $d$ not exceeding $n$.


Since you have resolved your issue, let me explain the above. We have $$\sum_{k=1}^n t(k) = \sum_{k=1}^n \sum_{\substack{1 \le d \le n \\ d|k}} 1$$ and we want to swap the order of summation. Well, as $k$ and $d$ range over $1$ to $n$, you add $1$ every time $d$ divides $k$. This is the same as adding $1$ every time $k$ is a multiple of $d$. For a fixed $d$, how many multiples of $d$ are there between $1$ and $n$? Precisely $\lfloor n/d \rfloor$ (they are $d$, $2d$, $3d$, ..., $md \le n < (m+1)d$). So $$\sum_{k=1}^n \sum_{\substack{1 \le d \le n \\ d|k}} 1 = \sum_{d=1}^n \sum_{\substack{1 \le k \le n\\ k = md}} 1 = \sum_{d=1}^n \Big\lfloor \frac{n}{d} \Big\rfloor$$ and the proof is complete.

$\endgroup$
  • $\begingroup$ I'm guessing that the first column counts what I wanted it to count... namely $n$. And this is the only extra term in my sum, since the other $1$'s are counting the $H_{k}$. Is this correct thinking? $\endgroup$ – Fred Apr 19 '16 at 6:12
  • $\begingroup$ I don't see the need to introduce $H_k$ and factorials at all. $\endgroup$ – Unit Apr 19 '16 at 6:17
  • $\begingroup$ I am using $n!$ because it's the only way I know how to relate the right-hand and left-hand sides of the sum. That is, it looked familiar to me from the fact that the highest power of $k$ that divides $n!$ is $\Sigma_{j=1}^{N_{k}} \lfloor n/(k^{j}) \rfloor$. This fact I've gotten from a different problem. $\endgroup$ – Fred Apr 19 '16 at 6:34
  • 1
    $\begingroup$ Don't look at the different problem, just look at what Unit has done! $\endgroup$ – Gerry Myerson Apr 19 '16 at 7:08
  • $\begingroup$ Right. According to this more general identity, we get that $$\sum_{n=1}^x \sum_{d|n} 1 = \sum_{d=1}^x \sum_{n=1}^{\lfloor x/d \rfloor} 1 = \sum_{d=1}^x \lfloor x/d \rfloor.$$ $\endgroup$ – mds May 24 '18 at 20:29
0
$\begingroup$

it is the basic theory of Dirichlet convolution : $$\zeta(s) = \sum_{n=1}^\infty n^{-s}$$ $$\zeta(s)^2 = (\sum_{n=1}^\infty n^{-s})(\sum_{m=1}^\infty m^{-s} )= \sum_{n=1}^\infty \sum_{m=1}^\infty n^{-s} m^{-s}= \sum_{n=1}^\infty n^{-s} \sum_{d|n} 1 = \sum_{n=1}^\infty \tau(n) n^{-s}$$ there is talso the Perron formula : $$\sum_{n=1}^\infty a_n n^{-s} = \int_{1-\epsilon}^\infty (\sum_{n=1}^\infty a_n \delta(x-n)) x^{-s} dx = s \int_1^\infty (\sum_{n \le x} a_n) x^{-s-1}dx$$ (integration by part)

hence

$$\zeta(s) = s \int_1^\infty (\sum_{n \le x}1) x^{-s-1} dx = s \int_1^\infty \lfloor x \rfloor x^{-s-1} dx$$

$$\zeta(s)^2 = s \int_1^\infty (\sum_{n \le x}\tau(n)) x^{-s-1} dx$$

but you can also write

$$\zeta(s)^2 = (\sum_{n=1}^\infty n^{-s} )s \int_1^\infty \lfloor x \rfloor x^{-s-1} dx = s \int_1^\infty (\sum_{n=1}^\infty \lfloor x/n \rfloor) x^{-s-1}dx$$ (since $\int_0^\infty f(x/n) x^{-s-1}dx = n^{-s} \int_0^\infty f(y) y^{-s-1}dy$ with $x= ny$)

i.e.

$$\sum_{n \le x}\tau(n) = \sum_{n=1}^\infty \lfloor x/n \rfloor = \sum_{n \le x} \lfloor x/n \rfloor$$

$\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.