# Solving a summation where the inner summation is limited by the iterator of the two outer summations

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{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{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}$

• "I would be able to solve this easily": are you so sure ? – Yves Daoust Jan 21 '15 at 9:42
• 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. – Yves Daoust Jan 21 '15 at 9:44
• 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. – Daniel Ong Jan 21 '15 at 10:24
• Do you confirm the $i\lfloor\sqrt j\rfloor$ interpretation ? – Yves Daoust Jan 21 '15 at 10:27

## 1 Answer

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.

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