# Are there a formula for generalize nested summation?

I have played a game that have a mechanic of summation and want to write algorithm to calculate it

It is a game that let you grow an insect nest. It has Ant that give you 1 food per sec. Queen give you 1 Ant per sec. Nest give you 1 Queen per sec

And so for simplicity I would make it start with 1 nest the formula would be

$$\sum_{i=0}^s 1 = s\\\text{for Queen I would get from 1 nest}$$ $$\sum_{i=0}^s i = \frac{s^2 + s}{2}\\\text{for Ant I would get from queens hatched from 1 nest}$$ $$\sum_{i=0}^s \frac{i^2 + i}{2} = \frac{1}{2} (\sum_{i=0}^s i^2 + \sum_{i=0}^s i) = \frac{s^3 + 3s^2 + 2s}{6}\\\text{for Food I would get from ants hatched so far}$$

It seem like there should be able to write formula or algorithm for any depth. Are there any formula like that exist?

So we can define $s_0(n) = 1, s_{m+1}(n) =\sum_{i=1}^n s_m(i)$.

You have calculated $s_1(n) = n, s_2(n)= \dfrac{n^2+n}{2}, s_3(n) = \dfrac{n^3+3n^2+2n}{6}$.

Note that $s_2(n)= \dfrac{n(n+1)}{2}$ and $s_3(n) = \dfrac{n(n^2+3n+2)}{6} = \dfrac{n(n+1)(n+2)}{6}$.

Do you see the pattern here?

Hint:

$s_4(n) = \dfrac{n(n+1)(n+2)(n+3)}{24}$.

Make a conjecture and try to prove it, by induction of course.

• Oh man why it seem (n + p)!/p!n! come out here... Dec 25 '17 at 2:58
• Do you have any source of mathematician who come up with this first? Dec 25 '17 at 2:59
• Euler at the latest, possibly Fermat or that era. Dec 26 '17 at 19:59
• Thanks. Does this formula has a name? Dec 27 '17 at 14:31

Faulhaber's formula might be relevant, see https://en.wikipedia.org/wiki/Faulhaber%27s_formula