Combinatorial proof that binomial coefficients are given by alternating sums of squares?

Question

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?

Answer 1

More a visual proof than combinatorial, perhaps:

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

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}$$

Answer 2

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.

Answer 3

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,

Answer 4

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.