Some thoughts on 1+2+3+…

This post is a rather dumb one – and, contrary to the title, the emphasis is not on 1+2+3+\cdots. In fact, I just put some of my dumb thoughts here after reading a comment of Terry Tao in his own post “Ask yourself dumb questions – and answer them!”, in response to a reader’s comment. (I definitely recommend Terry’s career advice, by the way. ) In short, in his post Terry tells us to be unafraid of asking (seemingly) stupid questions to test our own understanding and to explore all the possibilities. One reader asked him to give examples of dumb questions about an easy problem, such as {1+2+\cdots +n}. Terry Tao gave an amazing answer (which, due to some typesetting I will simply take the screenshot):

tao

Terry mentioned many questions that I haven’t thought about before, and I don’t think I will spend a lot of time thinking about them. However, the main point is that, even for some mathematics that are not at a very advanced level (I’m sure many young kids know that {1+\cdots +n=\frac{n(n+1)}{2}}), we can still learn a great deal by thinking more deeply. This is perhaps not emphasized enough in our (math) education, especially in secondary school, in which memorizing standard methods and formulas will be good enough most of the time. (That said, I had a very good math teacher back to the time when I was in secondary school. However, perhaps the style of the exams forces some students to memorize a lot of “facts”, as they think these are the (only) “right answers”. )

Anyway, as a dumb person, I will share some of the dumb thoughts about one of the questions Terry mentioned: finding the generalization of {1+\cdots +n=\frac{n(n+1)}{2}} in a combinatorial viewpoint. First, we will give a combinatorial proof of this theorem:

Theorem 1 {1+ 2+\cdots +n = \frac{n(n+1)}{2}}

Proof: The idea is that we count the number of ways of choosing two objects out of {n+1} objects, in which the order does not matter, in two ways. Let’s do it on the set {\lbrace 1, \cdots, n+1\rbrace}, as follows. Each choice is of the form {(k_1, k_2)}, where {1\le k_1< k_2\le n+1}. Suppose {k_1=1}, then there are {n} such choices, which amounts to choosing {k_2} from {\lbrace 2, \cdots, n+1\rbrace}. Similarly there are {n-1} choices for k_2 when {k_1=2}, and so on. On the other hand, as {{n+1} \choose 2} is the number of combinations of choosing {2} out of {n+1} objects, we have

\displaystyle {{n+1}\choose 2} = n+(n-1)+ (n-2)+\cdots +1=\sum_{i=1}^n i.

It is of course well-known that {{{n+1} \choose 2}=\frac{n(n+1)}{2}} (think of putting two different numbers in two slots, there are {n+1} choices for the first, and {n} choices for the second after the first choice is fixed, modulo the ordering (2!) of these pairs). Therefore

\displaystyle 1+\cdots +n=\frac{n(n+1)}{2}.

\Box

Of course, it is not any kind of hard stuff; Gauss discovered it when he was a child. Well, perhaps we can ask if there are any other sums which correspond to {{n+1}\choose r}. Of course there are, if we examine the above proof.

Say, let’s see if {{n+1}\choose 3} can be expressed as a sum. As above, the choices of choosing {3} numbers out of {\lbrace 1, \cdots, n+1\rbrace} are of the form {(k_1, k_2, k_3)}, where {1\le k_1<k_2<k_3\le n+1}. If {k_1=1}, there are {n\choose 2} choices. If {k_1=2}, there are {{n-1}\choose 2} choices, and so on. Therefore

\displaystyle {{n+1}\choose 3}={n\choose 2}+{{n-1}\choose 2}+ \cdots + {2\choose 2}=\sum _{k=2}^n {k\choose 2}.

This looks nice. And of course, in view of the above result, we can also express it as

\displaystyle {{n+1}\choose 3}=\sum _{k=1}^{n-1} \sum_{i=1}^{k}i.

We now define {s_1(n)=\overbrace {1+1+\cdots +1}^n=n} and {s_2(n)=1+2+\cdots +n = s_1(1)+s_1(2)+\cdots +s_1(n)}. Inductively, we define

\displaystyle s_{k+1}(n)= s_k (1)+ s_k(2)+ \cdots + s_k(n).

Then the above can be easily generalized to

\displaystyle {{n+1}\choose {k+1}}=s_{k+1}(n-k+1).

Expanding this, we get a formula for a repeated sum:

\displaystyle {{n+1}\choose {k+1}}=\overbrace {\sum_{i_k=1}^{n-k+1}\sum _{i_{k-1}=1}^{i_k}\cdots \sum_{i_1=1}^{i_2}}^{k}i_1=\overbrace {\sum_{i_k=1}^{n-k+1}\sum _{i_{k-1}=1}^{i_k}\cdots \sum_{i_0=1}^{i_1}}^{k+1}1. \ \ \ \ \ (1)

There is an interesting geometric interpretation of the RHS of (1), i.e. {s_{k+1}=\sum_i s_k(i)}, as counting the number of lattice points (i.e. points with integer coordinates) of a {k+1}-dimensional simplex (pyramid) (this is closely related to the fact that the {k+1}-dimensional “pyramid” of side {l}, obtained by {\displaystyle\lbrace x=(x_1, \cdots, x_k)\in \mathbb R^k: x_i\ge 0, \sum_{i=1}^k x_i \le l \rbrace} has {k}-dimensional volume {\frac{l^k}{k!}}, and that {\int_0^l x^{k-1}dx=\frac{l^k}{k}}. Indeed, by taking “limit version” of (1), we can obtain the repeated integral {\displaystyle\int_{x_k=0}^l\int_{x_{k-1}=0}^{x_k}\cdots \int_{x_1=0}^{x_2}1\,dx_1\cdots dx_k= \frac{l^k}{k!}}, which represents the {k}-dimensional volume of a certain pyramid. ). To illustrate this, this picture demonstrates the formula s_2(3)={4\choose 2}=6:

pyram1

This picture demonstrates the fact that s_3(3)={5\choose 3}=10:

pyram2

This picture demonstrates s_3(50)={52\choose 3} (it would be amazing if you can count the number of points in this pic :-P):pyram50

The “limiting case” for k=3 gives the volume of this pyramid:
pyram3

Advertisements
This entry was posted in Combinatorics. Bookmark the permalink.

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