0

I am trying to evaluate the following expression: $$(1)+(1+2)+(1+2+3)+(1+2+3+4)+...+(1+2+3+4+...+(N-1)+N) \\ =\sum\limits_{n=1}^N\frac{n(n+1)}{2}$$ Hopefully someone can give me a closed-form solution, otherwise just a general idea of whether this is exponential or super-exponential would help as well.

Thank you in advance.

高田航
  • 2,125
  • 13
  • 30

3 Answers3

1

Guide:

$$\sum_{n=1}^N \frac{n(n+1)}{2}=\frac12\left(\sum_{n=1}^N n^2 + \sum_{n=1}^N n \right)$$

Evaluating the last two summation should be manageable.

Complexity is cubic.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
1

This sum is $$\binom{2}2+\binom{3}2+\binom{4}2+\cdots+\binom{N+1}2$$ and such sums of binomial coefficients are also binomial coefficients, in this case $\binom{N+2}3$.

Angina Seng
  • 158,341
1

I would use "Newton's divided difference method" which is similar to a MacLaurin series except that it uses finite differences rather than derivatives. If we calculate f(n), $\Delta f(n)= f(n+1)- f(n)$, $\Delta^2 f(n)= \Delta f(n+ 1)- \Delta f(n+1)$, $\Delta^3 f(n)= \Delta^2 f(n+1)- \Delta^2(n)$, etc. Then $f(N)= f(0)+ \Delta f(0) N+ (1/2!)\Delta^2(0) N(N- 1)+ (1/3!)\Delta^3(0) N(N-1)(N-2)+ \cdot\cdot\cdot$.

Here, f(0)= 0, f(1)= 1, f(2)= 1+ 3= 4, f(3)= 1+ 3+ 6= 10, f(4)= 1+ 3+ 6+ 10= 20, f(5)= 1+ 3+ 6+ 10+ 15= 35, and f(6)= 1+ 3+ 6+ 10+ 15+ 21= 56. That should be enough to start.

Now, $\Delta f(0)= 1- 0= 1$, $\Delta f(1)= 4- 1= 3$, $\Delta f(2)= 10- 4= 6$, $\Delta f(3)= 20- 10= 10$, $\Delta f(4)= 35- 20= 15$, and $\Delta f(5)= 56- 35= 21$. (Those are, of course, the "n(n+1)/2" that we are adding.)

So $\Delta^2 f(0)= 3- 1= 2$, $\Delta^2 f(1)= 6- 3= 3$, $\Delta^2 f(2)= 10- 6= 4$, $\Delta^2 f(3)= 15- 10= 5$, and $\Delta^2 f(4)= 21- 16= 6$.

Finally, $\Delta^3 f(0)= 3- 2= 1$, $\Delta^3 f(1)= 4- 3= 1$, and $\Delta^3 f(2)= 5- 4= 1$, and $\Delta^3 f(3)= 6- 5= 1$.

Those are all 1 so obviously all successive differences will be 0. Applying Newton's divided difference formula (there is no actual "dividing" here since the difference between successive "N"s is 1) we have $f(N)= 0+ (1)N+ (1/2)(2)N(N-1)+ (1/6)(1)N(N- 1)(N- 2)$ $f(N)= (1/6)(6N+ 6N^2- 6N+ N^3- 3N^2+ 2N)= \frac{N^3+ 3N^2+ 2N}{6}$.

user247327
  • 18,710