## Monday Math 138

Show that $\sum\limits_{k=1}^{n}k(n+1-k)=\sum\limits_{k=1}^{n}\frac{k(k+1)}2$.

We have three ways to prove this. The first proof is algebraic: we find an explicit expression in terms of n for both sides. So, we use Faulhaber’s formula. We recall
$\sum\limits_{k=1}^{n}k=1+2+\cdots+n=\frac{n(n+1)}2$
and
$\sum\limits_{k=1}^{n}k^2=1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}6$
Thus, for the left-hand side, we have
$\begin{array}{rcl}\sum\limits_{k=1}^{n}k(n+1-k)&=&\sum\limits_{k=1}^{n}(n+1)k-k^2\\&=&(n+1)\left(\sum\limits_{k=1}^{n}k\right)-\left(\sum\limits_{k=1}^{n}k^2\right)\\&=&(n+1)\frac{n(n+1)}2-\frac{n(n+1)(2n+1)}6\\&=&\left(3(n+1)-(2n+1)\right)\frac{n(n+1)}6\\\sum\limits_{k=1}^{n}k(n+1-k)&=&\frac{n(n+1)(n+2)}6\end{array}$.
Now, for the right-hand side, we have
$\begin{array}{rcl}\sum\limits_{k=1}^{n}\frac{k(k+1)}2&=&\frac12\left(\sum\limits_{k=1}^{n}k^2\right)+\frac12\left(\sum\limits_{k=1}^{n}k\right)\\&=&\frac12\left(\frac{n(n+1)(2n+1)}6\right)+\frac12\left(\frac{n(n+1)}2\right)\\&=&\left((2n+1)+3\right)\frac{n(n+1)}{12}\\&=&(2n+4)\frac{n(n+1)}{12}\\\sum\limits_{k=1}^{n}\frac{k(k+1)}2&=&\frac{n(n+1)(n+2)}6\end{array}$,
and so the two are equal.

The second proof requires a little combinatorial thinking. We see from Faulhaber’s formula that the summand on the right is the kth triangular number:
$\frac{k(k+1)}2=1+2+3+\cdots+k=\sum\limits_{i=1}^{k}i$.
So we can rewrite the right-hand sum as
$\sum\limits_{k=1}^{n}\sum\limits_{i=1}^{k}i=(1)+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)$.
Now, in the expansion on the right above, how many times does each number appear in the sum? We see that 1 occurs n times, once in all n inner sums; 2 occurs n-1 times, once in all n inner sums except the first; 3 occurs n-2 times, once in all n inner sums except the first and second; and so on. Thus, the value k, 1≤kn occurs n+1-k times in each sum, so combining all the k terms, we have the contribution of $k(n+1-k)$ to the sum for each k, and so the total sum is $\sum\limits_{k=1}^{n}k(n+1-k)$, and we have proved our statement again.

The third proof comes from interpreting the sums geometrically. Consider a set of objects, such as spheres, packed into a tetrahedron with n per edge, like seen in the figure below for n=4:

If we slice this array parallel to a pair of opposing edges, the slices are rectangles, as done via the colors below

We see then that the rectangles go $1\times{n},\;2\times(n-1),\;3\times(n-2),\;\cdots,\;(n-2)\times3,\;(n-1)\times2,\;n\times1$, and so the total number of objects is $\sum\limits_{k=1}^{n}k(n+1-k)$.
But we can also slice the tetrahedron parallel to a face, as done with the base in the figure below:

And we see we have triangles; the first n triangles, and so the number of objects is the sum of the first n triangular numbers:
$\sum\limits_{k=1}^{n}\frac{k(k+1)}2$,
and our third proof is complete.

Note that we have found that the nth tetrahedral number is $T_n=\frac{n(n+1)(n+2)}6=\left({{n+2}\atop{3}}\right)$.