3
$\begingroup$

Does a closed form exist for the following sum? $$\sum_{k=0}^n \lfloor \sqrt{k} + \sqrt{k + n} \rfloor$$

If not, why is this sum so radically different than the sums below?

Closed forms do exist for the following sums*: $$\sum_{k=0}^n \lfloor \sqrt{k + n} \rfloor$$ $$\sum_{k=0}^n \lfloor \sqrt{k} \rfloor$$

There is this floor functional identity: $$\lfloor \sqrt{k} + \sqrt{k + 1} \rfloor = \lfloor\sqrt{4k+2}\rfloor$$ Don't know if this will help.

Thanks

*Existing closed forms

$$\sum_{k=0}^n \lfloor \sqrt{k} \rfloor=2\left(\sum_{k=0}^{\lfloor \sqrt{n} \rfloor-1}k^2\right)+\left(\sum_{k=0}^{\lfloor \sqrt{n} \rfloor-1}k\right)+\lfloor\sqrt{n}\rfloor\left(n-\lfloor\sqrt{n}\rfloor^2+1\right)$$ $$\left(\sum_{k=0}^n k^2\right)=\frac{2n^3+3n^2+n}{6}$$ $$\left(\sum_{k=0}^n k\right)=\frac{n^2+n}{2}$$ $$\sum_{k=1}^n \lfloor \sqrt{k+C} \rfloor=\sum_{k=C+1}^{C+n} \lfloor \sqrt{k} \rfloor=\sum_{k=0}^{C+n} \lfloor \sqrt{k} \rfloor-\sum_{k=0}^{C} \lfloor \sqrt{k} \rfloor$$

$\endgroup$
  • $\begingroup$ Interested to know which are the two closed forms you mention . $\endgroup$ – G Cab Aug 11 '17 at 11:18
  • $\begingroup$ I added the two closed forms. It is quite a mouth full, I will recheck it in an hour or so to make sure there are no mistakes $\endgroup$ – Ruan Sunkel Aug 11 '17 at 12:40
  • $\begingroup$ I am interested in this because$$\sum_{k=0}^{\left(\frac{n-1}{2}\right)^2} \lfloor \sqrt{k} + \sqrt{k + n} \rfloor - \sum_{k=0}^{\left(\frac{n-1}{2}\right)^2} \lceil \sqrt{k} + \sqrt{k + n} \rceil + \left(\frac{n-1}{2}\right)^2$$ counts the number of times an odd integer n can be written as the product of 2 integers. There probably is no closed-form, but it would be very nice. $\endgroup$ – Ruan Sunkel Aug 12 '17 at 20:23
  • $\begingroup$ If there is no closed-form expression, this type of thing is your classical chicken-egg scenario. For example, I want to use this formula to test the primality of n, but to evaluate the sum, I must know the primality of n. And in general, if I want to factor n using this formula, I must know the factors of n beforehand. $\endgroup$ – Ruan Sunkel Aug 12 '17 at 20:27
1
$\begingroup$

The "difference" is actually that $$ \eqalign{ & \left\lfloor {x + y} \right\rfloor = \cr & = \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor {\left\{ x \right\} + \left\{ y \right\}} \right\rfloor = \cr & = \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left[ {1 - \left\{ x \right\} \le \left\{ y \right\}} \right] \cr} $$ where $$ x = \left\lfloor x \right\rfloor + \left\{ x \right\} $$ and where $[P]$ denotes the Iverson bracket

So $$ \eqalign{ & \left\lfloor {\sqrt k + \sqrt {k + n} } \right\rfloor = \cr & = \left\lfloor {\sqrt k } \right\rfloor + \left\lfloor {\sqrt {k + n} } \right\rfloor + \left[ {1 - \left\{ {\sqrt k } \right\} \le \left\{ {\sqrt {k + n} } \right\}} \right] \cr} $$ and since you know the first two terms, the difficulty is to establish when the condition in the Iverson bracket is met.

$\endgroup$
  • $\begingroup$ Am I correct in saying that, if we know the factorization of n, then we know when the condition in the Iverson bracket is met, meaning we know for what k, $\sqrt{k}$ and $\sqrt{k+n}$ are integers, could we construct a closed form then? $\endgroup$ – Ruan Sunkel Aug 24 '17 at 14:02
  • $\begingroup$ My answer was mainly addressed to explain why knowing the sum for $\left\lfloor x \right\rfloor$ and $\left\lfloor y \right\rfloor$ does not help much in finding the sum of $\left\lfloor x+y \right\rfloor$. Of course you could use that to calculate the sum, but doubt very much you can arrive to a nice form. For that purpose the approach suggested by Yves is more neat and effective. $\endgroup$ – G Cab Aug 24 '17 at 18:52
  • $\begingroup$ Ok, I understand, thanks $\endgroup$ – Ruan Sunkel Aug 30 '17 at 15:20
0
$\begingroup$

Hint:

Such sums are made of runs of equal values, that are delimited by the indexes such that the general term crosses an integer.

$$\sqrt k+\sqrt{k+n}=m$$ when

$$k+2\sqrt k\sqrt{k+n}+k+n=m^2$$ or $$4k(k+n)=(m^2-n-2k)^2$$

or

$$k=\frac{(m^2-n)^2}{m^2}=m^2-2n+\frac1{m^2}.$$

As $k$ is an integer, the final fraction can be ignored and a run of weight $m$ has length $(m+1)^2-2n-m^2+2n=2m+1$.

Hence for complete runs, i.e. up to some $k^*=(m+1)^2-2n$ (excluded), the sum is that of $(2m+1)m$.

For the last incomplete run, the length is $n-k^*$, for weight $m+1$.

$\endgroup$
  • $\begingroup$ Thanks for the hint, I understand it, but I don't understand the rest completely. In this specific case it does not seem like the values are delimited by the indexes such that the general term crosses an integer. The general term crosses an integer when both k and k+n are square, but there are runs of different values between points, and there seem to be no obvious pattern. $\endgroup$ – Ruan Sunkel Aug 12 '17 at 18:56

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.