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).

Advertisements

Tags: , ,

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s


%d bloggers like this: