Sum of first $n$ triangle numbers, without induction

Question

Background

I wish to calculate $$ S= \sum_{i = 1}^{n}\frac{k(k+1)}{2}$$

I know what the answer is going to be, since this is essentially the sum of the first $n$ triangle numbers.

I.e. $S = (1) + (1+2) + (1+2+3) + \cdots + (1+2+3+\cdots+n)$

All solutions I've seen seem to know in advance what the answer is going to be, and their problem is proving it, which can be done using induction.

Question

However, I was wondering if this can be calculated using formulae for summations instead?

Alternatively, for instances where we do wish to prove it instead of calculate it, are there any other ways besides induction?

For reference

The answer should be $$\frac{n(n+1)(n+2)}{6}$$

Answer 1

If you know: $$ \sum\limits_{k=1}^n k = \frac{n(n+1)}{2} $$ and $$ \sum\limits_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} $$ then: $$ \sum\limits_{k=1}^n \frac{k(k+1)}{2} = \frac{1}{2} \left[\sum\limits_{k=1}^n k^2 + \sum\limits_{k=1}^n k \right] = \frac{1}{2}\left[\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\right] = \frac{n(n+1)(n+2)}{6} $$

Answer 2

Hint

$$\frac{k(k+1)}{2}=\sum_{j=1}^k j.$$ Therefore, your sum is $$\sum_{k=1}^n\sum_{j=1}^k j=\sum_{j=1}^n\sum_{k=j}^n j=\sum_{j=1}^n (n-j+1)j=n\sum_{j=1}^nj-\sum_{j=1}^n j^2+\sum_{j=1}^n j.$$

You have all elements to answer.

Answer 3

Instead of working forwards, work backwards:

$$\begin{align} \sum_{k=1}^n\frac{k(k+1)}{2} & = \sum_{k_1=1}^n\sum_{k_2=1}^{k_1}k_2 \\ & = \sum_{k_1=1}^n\sum_{k_2=1}^{k_1}\sum_{k_3=1}^{k_2}1 \\ \end{align}$$

This can be thought as a combinatoric problem and simply reduces to:

$$\frac{(n+2)!}{3!(n-1)!}=\frac{n(n+1)(n+2)}{6}$$

It is the number of ways you can choose $3$ elements from $n+2$ elements. For example, the number of ways you can choose $3$ letters from $\lbrace a,b,c,d,e,f\rbrace$ can be shown as

$$\underbrace{(abc,abd,abe,abf)}_4,\underbrace{(acd,ace,acf)}_3,\underbrace{(ade,adf)}_2,\underbrace{(aef)}_1$$

The number of ways can be thought of as $4+3+2+1=1+(1+2)+(1+2+3)=10$ or $_5C_3=\frac{5!}{3!(5-3)!}=\frac {120}{12}=10$

---

This method can be generalized to

$$\sum_{k_1=1}^r\sum_{k_2=1}^{k_1}\sum_{k_3=1}^{k_2}\dots\sum_{k_{n-1}=1}^{k_{n-2}}\sum_{k_n=1}^{k_{n-1}}1=\frac{(r+n-1)!}{n!(r-1)!}$$

which means the number of ways to choose $n$ elements from $r+n$ elements.

Answer 4

A telescopic approach: $$S= \sum_{i = 1}^{n}\frac{k(k+1)}{2}= \frac{1}{6}\sum_{i = 1}^{n}[(k+1)^3-k^3-1]= \frac{1}{6}\left[\sum_{i = 1}^{n}[(k+1)^3-k^3]-n\right]\\=\frac{1}{6}\left[(n+1)^3-1-n\right]=\frac{(n+1)}{6}\left[(n+1)^2-1\right]=\frac{(n+1)(n+2)n}{6}.$$

Answer 5

You are summing Binomial coefficients. In this case the relevant identity is $$\binom{2}{2}+\binom{3}{2}+\cdots +\binom{n}{2}=\binom{n+1}{3}$$ This method admits much generalization.

For example $n^3=\binom{n}{1}+6\binom{n}{2}+6\binom{n}{3}$

Answer 6

Another way to deal with your sum, and in general with the sum of the binomial coefficient in the upper index, is to consider that $$ \Delta _{\,n} \left( \begin{gathered} n \\ m \\ \end{gathered} \right) = \left( \begin{gathered} n + 1 \\ m \\ \end{gathered} \right) - \left( \begin{gathered} n \\ m \\ \end{gathered} \right) = \left( \begin{gathered} n \\ m - 1 \\ \end{gathered} \right) $$ So $$ \sum\limits_{a\,\, \leqslant \,k\, \leqslant \,b} {\left( \begin{gathered} k \\ m \\ \end{gathered} \right)} = \sum\limits_{a\,\, \leqslant \,k\, \leqslant \,b} {\Delta _{\,n} \left( \begin{gathered} k \\ m + 1 \\ \end{gathered} \right)} = \left( \begin{gathered} b + 1 \\ m + 1 \\ \end{gathered} \right) - \left( \begin{gathered} a \\ m + 1 \\ \end{gathered} \right) $$ and in your case $$ \sum\limits_{1\,\, \leqslant \,k\, \leqslant \,n} {\left( \begin{gathered} k + 1 \\ 2 \\ \end{gathered} \right)} = \sum\limits_{2\,\, \leqslant \,j\, \leqslant \,n + 1} {\left( \begin{gathered} j \\ 2 \\ \end{gathered} \right)} = \left( \begin{gathered} n + 2 \\ 3 \\ \end{gathered} \right) - \left( \begin{gathered} 2 \\ 3 \\ \end{gathered} \right) = \left( \begin{gathered} n + 2 \\ 3 \\ \end{gathered} \right) $$