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

Solution 1:

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

Solution 2:

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)$$