10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Unlikely; see the related math.stackexchange.com/q/384520/73324 $\endgroup$ – vadim123 Jun 7 '13 at 18:47
  • $\begingroup$ @Martin, is the sequence formed by these sums not a sequence? $\endgroup$ – Antonio Vargas Dec 1 '16 at 17:38
  • $\begingroup$ @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." $\endgroup$ – Martin Sleziak Dec 1 '16 at 17:41
17
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

enter image description here

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


Comparison with Marko Riedel's Answer

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

enter image description here

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.

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