Sums involving floor function

Question

I am looking for a direct formula for this sum

$$\sum_{k=0}^n \lfloor{\sqrt{n+k}}\rfloor\lfloor{\sqrt{k}}\rfloor$$

Or a method to efficiently compute the sum for large n

Answer 1

I do not think that a closed form could exist.

Generating value for $100\leq n\leq 10000$ by step of $100$ and plotting the results shows something very close to a power law. Using nonlinear regression, what I obtained is $$S_n=\sum_{k=0}^n \lfloor{\sqrt{n+k}}\rfloor\lfloor{\sqrt{k}}\rfloor\approx 0.781411\, n^{2.0067}$$ where both parameters are highly significant as show below $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & 0.781411 & 0.000529556 & \{0.78036,0.782462\} \\ b & 2.006700 & 0.000075149 & \{2.00655,2.006850\} \\ \end{array} $$ I suppose that we could keep the exponent equal to $2$ and get $$S_n \approx 0.830070\, n^2$$

You should notice that, as Yves Daoust commented, $$\int_0^1\sqrt{1+x}\sqrt x \,dx=\frac{1}{4} \left(3 \sqrt{2}-\sinh ^{-1}(1)\right)\approx 0.840317$$