0
$\begingroup$

I'm trying to solve the following summation (where C is some constant) but I'm stuck because of the inner most summation which is limited by $i\sqrt[2]{j}$ where i and j are the iterators of the outer two summations. $$ \sum\limits_{i=1}^N \sum\limits_{j=1}^i \sum\limits_{k=1}^{i\sqrt[2]{j}}C $$

If that darned third summation didn't exist, I would be able to solve this easily but I have no idea how to deal with that third summation. Any thoughts?

edit: $i, j, k\in\mathbb Z_{> 0}$

$\endgroup$
  • $\begingroup$ "I would be able to solve this easily": are you so sure ? $\endgroup$ – Yves Daoust Jan 21 '15 at 9:42
  • $\begingroup$ The upper bound isn't well defined as it should be an integer. You can take one of $i\lfloor\sqrt j\rfloor$ and $\lfloor i\sqrt j\rfloor$, or even ceilings. $\endgroup$ – Yves Daoust Jan 21 '15 at 9:44
  • $\begingroup$ Thank you. I forgot to specify that i, j, k are integers and to include the floor function in the upper limit of the third summation but you spotted my mistake and correctly guessed what I meant in your solution. $\endgroup$ – Daniel Ong Jan 21 '15 at 10:24
  • $\begingroup$ Do you confirm the $i\lfloor\sqrt j\rfloor$ interpretation ? $\endgroup$ – Yves Daoust Jan 21 '15 at 10:27
1
$\begingroup$

The sum on $k$ just equals the constant times the number of terms. Assuming the integer square root, $$S= \sum\limits_{i=1}^N \sum\limits_{j=1}^i \sum\limits_{k=1}^{i\lfloor\sqrt{j}\rfloor}C = \sum\limits_{i=1}^N \sum\limits_{j=1}^i Ci\lfloor\sqrt{j}\rfloor = C\sum\limits_{i=1}^N i\sum\limits_{j=1}^i\lfloor\sqrt{j}\rfloor.$$

The sum on $j$ is uneasy and can be addressed by decomposing into sequences that yield the same square root. For convenience, we will approximate it as if it was an integral: $$S\approx C\sum\limits_{i=1}^N i\left(\frac23i^{3/2}\right).$$ And finally for the sum on $i$, $$S\approx C\frac4{21}N^{7/2}.$$


Summing integer square roots

When $l^2\le j<(l+1)^2$, we have $\lfloor\sqrt j\rfloor=l$. There are exactly $(l+1)^2-l^2=2l+1$ values of $j$ that achieve this. The range $(0,j)$ can be decomposed in the full subranges $(l^2,(l+1)^2-1)$, for $l$ in $(0,\lfloor\sqrt j\rfloor-1)$, and the final incomplete interval $(\lfloor\sqrt j\rfloor^2,j)$.

Hence,

$$\sum\limits_{j=1}^i\lfloor\sqrt j\rfloor=\sum_{l=0}^{\lfloor\sqrt i\rfloor-1}(2l+1)l+(i-\lfloor\sqrt i\rfloor^2+1)\lfloor\sqrt i\rfloor.$$

The sum on $l$ is derived from Faulhaber's formula as

$$2\sum_{l=0}^{\lfloor\sqrt i\rfloor-1}l^2+\sum_{l=0}^{\lfloor\sqrt i\rfloor-1}l=2\frac{2\lfloor\sqrt i\rfloor^3-3\lfloor\sqrt i\rfloor^2+\lfloor\sqrt i\rfloor}6+\frac{\lfloor\sqrt i\rfloor(\lfloor\sqrt i\rfloor-1)}2$$ This confirms the $\frac23i^{3/2}$ behavior.

$\endgroup$
  • $\begingroup$ The exact formula for $S$ can be derived by using a similar decomposition trick on $i$. Good luck! $\endgroup$ – Yves Daoust Jan 21 '15 at 10:28
  • $\begingroup$ Be sure I really enjoyed your approach and solution ! $\endgroup$ – Claude Leibovici Jan 21 '15 at 10:30
  • $\begingroup$ @ClaudeLeibovici: thumbs up! $\endgroup$ – Yves Daoust Jan 21 '15 at 10:32

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.