3
$\begingroup$

Is there a way to calculate the following sum for large $c>K$, closed-form or approximation?

$$\sum_{n=1}^{c}\left\{\sqrt{K+n^2}\right\}$$Where K and n are positive integers and $\{\}$ indicates the fractional part.

A similar question: Fractional part summation

$\endgroup$
3
  • $\begingroup$ Hint: when $n$ is large compared to $\sqrt K$ then $\sqrt{K+n^2}-n \sim \frac{K}{2n}$. $\endgroup$ Aug 22, 2021 at 20:30
  • $\begingroup$ @RuanSunkel are you satisfied with my answer? $\endgroup$
    – fwd
    Aug 24, 2021 at 13:20
  • $\begingroup$ Hi @fwd, I am still busy digesting. So far I am happy with the answer, I learned a lot. Looking at the question and the answer, I think what I am really interested in is the $\mathcal{O}(1)$ term in $\sum_2$, calculating it given a specific $K$ and $c$, so basically calculating the actual value of $\sum_2$. Thinking of maybe asking a follow up question. $\endgroup$ Aug 24, 2021 at 14:14

1 Answer 1

2
$\begingroup$

The given sum can be written as $$ \Sigma = \Sigma_1 - \Sigma_2 $$ where $$ \Sigma_1 = \sum_{n=1}^{c} \sqrt{n^2 + K} $$ and $$ \Sigma_2 = \sum_{n=1}^{c} \lfloor\sqrt{n^2 + K}\rfloor. $$ Now using $H_n = \log n + \gamma + \mathcal{O}(1/n)$ where $H_n$ is the $n$-th harmonic number, \begin{align*} \sum_{n=1}^{c} \sqrt{n^2 + K} - n &= \sum_{n=1}^c \frac{K}{\sqrt{n^2 + K} + n} \\ &\le \frac{K}{2} \sum_{n=1}^{c} \frac{1}{n} = \frac{K}{2}(\log c + \gamma + \mathcal{O}(1/c)). \end{align*} Hence $$ \Sigma_{1} = \sum_{n=1}^{c} \sqrt{n^2 + K} = \frac{1}{2}c(c+1) + \frac{K}{2}(\log c + \gamma) + \mathcal{O}(1/c) $$

Let $A = \lfloor\sqrt{K+1} - 1\rfloor$. Then, \begin{align*} \Sigma_{2} = \sum_{n=1}^{c} \lfloor\sqrt{n^2 + K}\rfloor &= \sum_{j=1}^{A}\sum_{\frac{K-(j+1)^2}{2(j+1)} < n \le \frac{K-j^2}{2j}}(n+j) + \sum_{\frac{K-1}{2} < n \le c}n \\ &= \sum_{n=1}^c n + \sum_{j=1}^{A}\sum_{\frac{K-(j+1)^2}{2(j+1)} < n \le \frac{K-j^2}{2j}}j\\ &= \frac{1}{2}c(c+1) + \sum_{j=1}^A j\left(\frac{3}{2} + \frac{K}{2j(j+1)}+ \mathcal{O}(1)\right)\\ &= \frac{1}{2}c(c+1) + \frac{3}{4}A(A+1) + \frac{K}{2}(H_A - 1) + \mathcal{O}\left(\sum_{j=1}^A j\right)\\ &= \frac{1}{2}c(c+1) + \frac{3}{4}A(A+1) + \frac{K}{2}(H_A - 1) + \mathcal{O}(1) \end{align*} since $\mathcal{O}\left(\sum_{j=1}^A j\right) = \mathcal{O}(K) = \mathcal{O}(1)$.

Thus,

\begin{align*} \Sigma &= \frac{K}{2}(\log c + \gamma) - \frac{3}{4}A(A+1) - \frac{K}{2}(H_A - 1) + \mathcal{O}(1).\\ \end{align*}

$\endgroup$
6
  • $\begingroup$ Hi, thank you for the answer. I did a quick test and $\sum_2$ seems to be different than expected. For example, with $K=15$, and $c=16$, $\sum_2=146$, but $\sum_2$ provided in the answer gives $\sum_2=2822$. Please correct me if I am missing something. $\endgroup$ Aug 22, 2021 at 18:14
  • $\begingroup$ you're right, something's wrong $\endgroup$
    – fwd
    Aug 22, 2021 at 19:07
  • $\begingroup$ @RuanSunkel I have edited my answer. $\endgroup$
    – fwd
    Aug 23, 2021 at 6:33
  • $\begingroup$ Thank you @fwd. Can you please elaborate on the $\mathcal{O}(1)$ constant that depends on $K$? $\endgroup$ Aug 23, 2021 at 17:57
  • $\begingroup$ @RuanSunkel I added more details to show where the $\mathcal{O}(1)$ term comes from. The larger $K$ is, the larger this term is. Numerical plots suggest that it grows linearly in $K$. But since $K$ is fixed, it's just $\mathcal{O}(1)$ $\endgroup$
    – fwd
    Aug 23, 2021 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .