0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

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

$\endgroup$

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.