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$
2
  • $\begingroup$ Interested to know which are the two closed forms you mention . $\endgroup$
    – G Cab
    Commented Aug 11, 2017 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$ Commented Aug 11, 2017 at 12:40

2 Answers 2

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$
3
  • $\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$ Commented Aug 24, 2017 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
    Commented Aug 24, 2017 at 18:52
  • $\begingroup$ Ok, I understand, thanks $\endgroup$ Commented Aug 30, 2017 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$
0

You must log in to answer this question.

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