Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A student recently asked whether there was a combinatorial proof of the following identity:

$\begin{equation*} \sum^n_{k=1}(-1)^{n-k}k^2 = {n+1 \choose 2}. \end{equation*}$

I was in a rush and couldn't come up with anything nice off the top of my head. Any ideas or pictures to make this clearer?

share|improve this question
add comment

4 Answers

up vote 10 down vote accepted

This is what I came up, (more a visual proof than combinatorial, perhaps).

$$ 5^2 - 4^2 + 3^2 -2^2 +1^2 = {6 \choose 2}$$

Visual proof

On the left, you have the alternating sum as an inclusion-exclusion of squares: the total sum is the number of coloured cells.

On the right, you have those L shaped shapes rearranged in the top left of a 6x6 grid. If you think of each cell as a coordinate $(x_1,x_2)$ that gives two elements chosen from the set $\{1, 2 \cdots 6\}$, it's seen that the elements are choosen with $ x_2 > x_1$, what corresponds to a combination (no repetition, and no order).

Added: The others are well known, but, just for the sake of completeness...

$$\displaystyle \sum_{k=1}^n (-1)^{n-k} k^2 = {n+1 \choose 2} = \sum_{k=1}^n \; k = \frac{(n+1) \; n}{2}$$

Visual proof 2

share|improve this answer
    
Nice. (Maybe we should, from the start, give to the L-shapes the orientation of the letter L, after all...) –  Did Jun 11 '11 at 14:27
    
Yeah, my L are really more like gammas... but I chose this orientation because it leads more nicely to the other grid with its indexes in my desired ordering. –  leonbloy Jun 11 '11 at 14:31
    
Very nice! (characters...) –  Jon Jun 11 '11 at 16:45
add comment

Get rid of the negative signs by putting together the two last terms of the sum, then the two last before these, and so on. The result is the area of a subset of the $n\times n$ square made of $1\times1$ squares composing L-shaped strips: the largest strip is the union of the $n$ column and the $n$ horizontal line, consecutive strips are separated by similar strips, each strip starts from the vertical axis of coordinates then goes East then goes South and ends at the horizontal axis of coordinates, and I hope that with these indications everybody can picture the result.

Now, color in black the strips composing the subset one wants to measure and color in white the rest of the rectangle:

$\blacksquare\blacksquare\blacksquare\blacksquare\blacksquare$
$\Box\Box\Box\Box\blacksquare$
$\blacksquare\blacksquare\blacksquare\Box\blacksquare$
$\Box\Box\blacksquare\Box\blacksquare$
$\blacksquare\Box\blacksquare\Box\blacksquare$

Next, add a white line of width $n$ to the top of the picture:

$\Box\Box\Box\Box\Box$
$\blacksquare\blacksquare\blacksquare\blacksquare\blacksquare$
$\Box\Box\Box\Box\blacksquare$
$\blacksquare\blacksquare\blacksquare\Box\blacksquare$
$\Box\Box\blacksquare\Box\blacksquare$
$\blacksquare\Box\blacksquare\Box\blacksquare$

The resulting rectangle has size $n\times(n+1)$ and I pretend that it is evenly colored. This will prove the result since its area is $n(n+1)$.

To show this, one can pair together sub-rectangles of opposite colors. The first pair is made of the whole line $n+1$ (white) and the whole line $n$ (black). Erase them both. The resulting rectangle has size $n\times(n-1)$:

$\Box\Box\Box\Box\blacksquare$
$\blacksquare\blacksquare\blacksquare\Box\blacksquare$
$\Box\Box\blacksquare\Box\blacksquare$
$\blacksquare\Box\blacksquare\Box\blacksquare$

Its last two columns have opposite colors, erase them both. The resulting rectangle has size $(n-2)\times(n-1)$ and it is the augmented rectangle one would consider to solve the $n-2$ case:

$\Box\Box\Box$
$\blacksquare\blacksquare\blacksquare$
$\Box\Box\blacksquare$
$\blacksquare\Box\blacksquare$

Either continue these erasure steps till the end (where one gets an evenly colored rectangle of size $1\times2$ if $n$ is odd and $2\times1$ if $n$ is even) or assume that the hypothesis holds at rank $n-2$, either way one is done.

Edit An alternative, maybe simpler, is to peel the $n\times(n+1)$ rectangle, starting from the top and right sides, one L-shape after the other. For example the first L-shape is the union of the $2n$ elementary squares in the last line and the last column.Then the result follows from the fact that these L-shapes are all evenly colored,

share|improve this answer
    
Well, yes, after grouping terms by 2 it becomes just a sum of arithmetic progression (which can be computed combinatorially, indeed). But is there (even more) combinatorial proof that avoids it, I wonder. –  Grigory M Jun 11 '11 at 12:58
    
@Grigory: What are you talking about? The method does not involve any computation of a sum of an arithmetic progression. If you read the post you will see that the first sentence of your comment does not apply. –  Did Jun 11 '11 at 13:14
    
Well, actually it does (it's essentially "geometric summation" of arithmetic progression). And perhaps my comment wasn't clear enough: "it" in "avoids it" referred to grouping terms by 2 (and not to the second part). –  Grigory M Jun 11 '11 at 13:25
    
@Grigory: The computations involved are first, that the area of a rectangle of size $a\times b$ is $ab$, and second (if one insists on calling this a computation), that if a set of size $N$ can be partitioned into two subsets $A$ and $B$ of equal size, then ($N$ is even and) the size of $A$ is $N/2$. Nothing else. –  Did Jun 11 '11 at 13:37
add comment

By induction. The formula holds for $n=0$ because both sides vanish.

You can also increase $n$ by one: $$LHS_n = n^2 - LHS_{n-1} = \dots $$ I had to add the last term $n^2$. However, the signs of all the previous terms were reverted because of the $(-1)^n$ factor, so I had to add a minus sign in front of $LHS_{n-1}$.

Assuming that the equation holds for $n-1$, i.e. that $LHS_{n-1}=RHS_{n-1}$, the displayed formula is $$ \dots = n^2 - RHS_{n-1} = n^2 - (n-1)n/2 = n(n+1) / 2 = RHS_n$$ which you wanted to be proved.

share|improve this answer
2  
The question asks for a combinatorial proof. –  joriki Jun 11 '11 at 12:00
    
Combinatorial? Pictures? –  Did Jun 11 '11 at 12:00
1  
OK, sorry, I probably don't know what a combinatorial proof is. If that's pictures, I was taught that the most beautiful picture is an equation. ;-) –  Luboš Motl Jun 11 '11 at 12:02
2  
add comment

We can use the very nice picture in the post of Didier Piau (without the added white line on top) and tell a somewhat different story.

Imagine that $n$ is odd, because the picture does. Things hardly change if $n$ is even.

First (and unimportantly) we change the story that led to the colouring. Reverse the addition, so that we are looking at $5^2-4^2+3^2-2^2+1^2$. If this "algebraic" trick is not combinatorial enough, we could work our way around it, but prefer not to.

By a $j \times j$ subsquare we mean the $j \times j$ square with bottom left corner the same as the bottom left corner of the original square.

Colour the full square black. Then colour the $(n-1)\times (n-1)$ subsquare white, then the $(n-2)\times(n-2)$ subsquare black, and so on. This inclusion-exclusion process mirrors exactly our alternating sum, and produces the black-white pattern of the picture.

Next we interpret the upside down and backwards black "L-shaped" figures. We want to end up with $\binom{n+1}{2}$.

Imagine choosing $2$ objects from the numbers $1$ to $n+1$. We have the following possibilities: (i) the biggest number used is $n+1$ or $n$; (ii) the biggest number used is $n-1$ or $n-2$; and so on.

Look at the largest black L-shaped figure. Its upper right-hand corner counts the choice $\{n, n+1\}$. The remaining horizontal black squares of the big L counts the choices $n-1$ choices $\{k,n+1\}$ with $k<n$. And the remaining vertical black squares of the big L counts the choices $(k,n)$ with $k<n$.

In the same way, the next black L-shaped figure counts the choice from the $n+1$ numbers, where the largest chosen number is $n-1$ or $n-2$. And so on.

share|improve this answer
    
Your explanation of the black-white pattern is in my post. After that, you present a nice explicit bijection betwen the set of pairs from $\{1,2,\ldots,n+1\}$ and the collection of black squares. –  Did Jun 11 '11 at 14:23
    
@Didier Piau: I misunderstood the explanation of the colouring, interpreting the "Get rid of the minus signs by putting together" as having a whiff of the algebraic. Anyway, that was not the point of the post, as I think I made clear. The point was interpreting the L-shaped black figures as counting choices. An interesting application of the general idea (but choosing $3$ objects) is showing bijectively that $2^2+4^2 + \cdots + (2n)^2=\binom{2n+2}{3}$. –  André Nicolas Jun 11 '11 at 14:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.