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
Thus, for the left-hand side, we have
Now, for the right-hand side, we have
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:
So we can rewrite the right-hand sum as
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:
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).


Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: