# Closed form of $\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor^2$?

Does $\displaystyle\sum_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor^2$ admit a closed form expression?

• Unlikely; see the related math.stackexchange.com/q/384520/73324 – vadim123 Jun 7 '13 at 18:47
• @Martin, is the sequence formed by these sums not a sequence? – Antonio Vargas Dec 1 '16 at 17:38
• @AntonioVargas The same could be said about any finite sum of the form $\sum_{k=1}^n a_n$. Of course, if you think that for some reasone the tag belongs there, you can edit it back. My understanding is that the tag-excerpt says rather clearly: "For questions on finite sums use the (summation) instead." – Martin Sleziak Dec 1 '16 at 17:41

To see how the first term in the asymptotic expansion is obtained, put $$a(n) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor^2$$ and note that $$a(n+1)-a(n) = 1 + \sum_{k=1}^n \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor^2 - \bigg\lfloor \frac{n}{k} \bigg\rfloor^2\right) \\= 1 + \sum_{d|n+1 \atop d<n+1} \left(\left(\frac{n+1}{d}\right)^2 - \left(\frac{n+1}{d}-1\right)^2\right) = \sum_{d|n+1} \left(2\left(\frac{n+1}{d}\right)-1\right) \\= 2\sigma(n+1)-\tau(n+1).$$

It now follows that $$a(n) = 2\sum_{k=1}^n \sigma(k) - \sum_{k=1}^n \tau(k) = \sum_{k=1}^n \left(2\sigma(k)-\tau(k)\right).$$ We can apply the Wiener-Ikehara theorem to this sum, working with the Dirichlet series $$L(s) = \sum_{n\ge 1} \frac{2\sigma(n)-\tau(n)}{n^s} = 2\zeta(s-1)\zeta(s)-\zeta(s)^2.$$ We have $$\operatorname{Res}(L(s); s=2) = \frac{\pi^2}{3},$$ so that by the aforementioned theorem, $$a(n) \sim \frac{\pi^2/3}{2} n^2 = \frac{\pi^2}{6} n^2.$$ In fact we can use Mellin-Perron summation to predict, but not quite prove, the next terms in the asymptotic expansion, getting $$a(n) = \left(\sigma(n)-\frac{1}{2}\tau(n)\right) + \frac{1}{2\pi i} \int_{5/2-i\infty}^{5/2+i\infty} L(s) n^s \frac{ds}{s}$$ which yields $$a(n) \sim \left(\sigma(n)-\frac{1}{2}\tau(n)\right) +\frac{\pi^2}{6} n^2 - (\log n + 2 \gamma)n - \frac{1}{6}.$$ This approximation is quite good, giving $16085.71386$ for $n=100$ when the correct value is $16116$ and $1639203.715$ for $n=1000$ when the correct value is $1639093.$

This is A222548 in the online encyclopedia of integer sequences. They don't provide a closed form, but they do give the following:

$$a(n)\approx\frac{\pi^2}{6}n^2+O(n\log n)$$

Let me complement @Marko Riedel's excellent answer by providing a low-tech approach to the leading term.

Let us denote by $\mathbf{1}\{\cdot\}$ the indicator function of the set $\{\cdot\}$. Then using the identity

$$\lfloor n/i \rfloor = \sum_{j=1}^{n} \mathbf{1}\{ij \leq n \}$$

we can rearrange the sum to find:

\begin{align*} a(n) &= \sum_{i=1}^{n} \sum_{\substack{1 \leq j \leq n \\ 1 \leq k \leq n}} \mathbf{1}\{ij \leq n\}\mathbf{1}\{ik \leq n\} = \sum_{\substack{1 \leq j \leq n \\ 1 \leq k \leq n}} \sum_{i=1}^{n} \mathbf{1}\Big\{i \leq \frac{n}{\max\{j,k\}}\Big\} \\ &= \sum_{\substack{1 \leq j \leq n \\ 1 \leq k \leq n}} \left\lfloor \frac{n}{\max\{j,k\}} \right\rfloor = \sum_{l=1}^{n} \sum_{\substack{1 \leq j \leq n \\ 1 \leq k \leq n}} \left\lfloor \frac{n}{l} \right\rfloor \mathbf{1}\{\max\{j,k\} = l\} \\ &= \sum_{l=1}^{n} (2l-1) \left\lfloor \frac{n}{l} \right\rfloor. \end{align*}

Dividing both sides by $n^2$, the RHS can be identified as Riemann sum and thus

$$\frac{a(n)}{n^2} = \sum_{l=1}^{n} \frac{2l-1}{n} \left\lfloor \frac{n}{l} \right\rfloor \frac{1}{n} \xrightarrow[\ n\to\infty \ ]{} \int_{0}^{1} 2x \left\lfloor\frac{1}{x}\right\rfloor \, dx = \zeta(2).$$

Here, the last integral can be easily computed by applying the substitution $x \mapsto 1/x$.

An Answer Without Number Theoretic Functions

Break up the sum as follows: $$\sum_{k=1}^n\left\lfloor\frac nk\right\rfloor^2 =\sum_{k=1}^n\frac{n^2}{k^2}-\sum_{k=1}^n\left(\frac{n^2}{k^2}-\left\lfloor\frac nk\right\rfloor^2\right)\tag{1}$$ We can apply the Euler-Maclaurin Sum Formula $$\sum_{k=1}^n\frac{n^2}{k^2}\sim n^2\left(\frac{\pi^2}6-\frac1n+\frac1{2n^2}\right)\tag{2}$$ If we note that $\left\{\frac nk\right\}\lt1-\frac1k$, we see that \begin{align} \sum_{k=1}^n\left(\frac{n^2}{k^2}-\left\lfloor\frac nk\right\rfloor^2\right) &=\sum_{k=1}^n\left(\frac nk-\left\lfloor\frac nk\right\rfloor\right)\left(\frac nk+\left\lfloor\frac nk\right\rfloor\right)\\ &=\sum_{k=1}^n\left\{\frac nk\right\}\left(2\frac{n}{k}-\left\{\frac nk\right\}\right)\\ &\le\sum_{k=1}^n\left(1-\frac1k\right)2\frac nk\\[9pt] &\le2n\log(n)\tag{3} \end{align} Therefore, by $(1)$, $(2)$, and $(3)$ we have $$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^n\left\lfloor\frac nk\right\rfloor^2=n^2\frac{\pi^2}6+O(n\log(n))}\tag{4}$$ However, if we use $\frac12{-}\frac1{2k}$ for the mean value of $\left\{\frac nk\right\}$ and $\frac13{-}\frac1{2k}{+}\frac1{6k^2}$ for the mean value of $\left\{\frac nk\right\}^2$ \begin{align} \sum_{k=1}^n\left(\frac{n^2}{k^2}-\left\lfloor\frac nk\right\rfloor^2\right) &=\sum_{k=1}^n\left(\frac nk-\left\lfloor\frac nk\right\rfloor\right)\left(\frac nk+\left\lfloor\frac nk\right\rfloor\right)\\ &=\sum_{k=1}^n\left\{\frac nk\right\}\left(2\frac{n}{k}-\left\{\frac nk\right\}\right)\\ &\approx\sum_{k=1}^n\left(\frac12-\frac1{2k}\right)2\frac{n}{k}-\left(\frac13-\frac1{2k}+\frac1{6k^2}\right)\\ &=n\log(n)+n\left(\gamma-\frac{\pi^2}6-\frac13\right)+O(\log(n))\tag{5} \end{align} Thus, if we look at the average behavior, we can use $(1)$, $(2)$, and approximation $(5)$ to get $$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^n\left\lfloor\frac nk\right\rfloor^2 \approx n^2\frac{\pi^2}6-n\log(n)+n\left(\frac{\pi^2}6-\gamma-\frac23\right)}\tag{6}$$

The value given by $(6)$ for $n=98$ is $15387.9230$ while the actual value is $15381$.
The value given by $(6)$ for $n=1001$ is $1641711.3692$ while the actual value is $1641772$.

The error of the approximation in $(6)$ appears to be proportional to $n$. Here is a plot of that error, for $1\le n\le3000$, divided by $n$:

The error divided by $n$ has a mean of $-0.0746805451$ and a standard deviation of $0.6513592109$.

Using number theoretic functions, Marko Riedel's answer gives a better approximation. Here is a plot of the error of that approximation, for $1\le n\le3000$, divided by $n$:
The error divided by $n$ has a mean of $0.0060900069$ and a standard deviation of $0.3674311090$. This is better than the error distribution in my answer, but it does require factoring $n$ to compute the number theoretic functions.