Two Combinatorial Proofs for Sums of Squares Formulas



Counting Squares to Sum Squares

Duane W. DeTemple

For a combinatorialist, the most beautiful proof is one obtained by counting. Indeed, as enthusiastically stated by Art Benjamin and Jennifer Quinn in [1], “… that kind of proof is the only right one.”

In this note we derive two identities involving sums of squares by literally counting squares. For the first identity, we count the number of geometric lattice squares in a square grid, where only those squares with sides aligned with the grid are considered. We derive the second identity by counting all of the lattice squares within a given square grid, including those with either aligned or tilted sides.

Counting Squares Aligned with a Grid of Unit Squares

Our goal is to prove that [pic]. Actually, we will prove the equivalent identity

[pic]. (A)

Our combinatorial proof is obtained by counting the number of aligned lattice squares in an n ( n grid of unit squares in two ways, so that equating the two counts proves the identity.

Count A1. Let [pic]. As shown by the solid dots in Figure 1, there are k2 positions for the lower left corner of any square of side length n + 1– k.

Thus the total number of aligned lattice squares is [pic].

Count A2. Any aligned square in the n ( n grid is uniquely described by the triple

(a, b, c) that gives the coordinates (a, b) of its lower left corner and the larger coordinate c of its upper right corner. Thus, we want to count the number of triples, [pic], in the set

[pic].

To determine [pic] in the desired form, we consider the peculiar but, as will be seen shortly, very helpful set

[pic].

It is easy to determine |T|: there are [pic] ways to choose {x, y} with x < y, and then

2n + 1 ways to choose a z that avoids x. Thus, [pic]. We now claim there is a one-to-three relation of S onto T. There are three cases, depending on whether the lower left corner of the square described by the triple (a, b, c) is (1) above, (2) below, or (3) on the main diagonal of the n ( n grid (see Figure 2).

Case 1: a < b < c

The triple (a, b, c) is mapped to three triples (x, y, z) from T, namely

(a, b, c), (a, c, b), and (b, c, a). Note that each (x, y, z) consists of three distinct values from {0, 1, 2, .. , n}, that x < y, and that [pic].

Case 2: b < a < c

The triple (a, b, c) is mapped to the three triples (x, y, z) from T :(b, a, c(), (a, c, b(), and (b, c, a(). Here (x, y, z) satisfies [pic].

Case 3: a = b < c

The triple (a, a, c) is mapped to three triples (x, y, z) from T : (a, c, a’), (a, c, c), and

(a, c, c(). Each (x, y, z) satisfies [pic].

The one-to-three correspondence from S onto T shows that the number of aligned lattice squares in the n ( n grid is [pic], thus proving (A).

In Case 1, we see that each of the[pic] triples (a, b, c) with

0 ( a < b < c ( n corresponds to a square with its lower left corner above the main diagonal, so there are 2[pic] squares whose lower left corners are either above or below the main diagonal of the square grid. In Case 3, each of the [pic] pairs (a, c) with 0 ( a < c ( n corresponds to a square with its lower left corner at (a, a) on the main diagonal and upper right corner at (c, c). This gives us the identity

[pic],

which was shown in [1] or which can be obtained by the method of difference sequences using Theorem 8.2.3 of Brualdi’s text [3, p. 283]. The form of identity (A) is more pleasing because it avoids sums.. Other counting proofs of (A) or its algebraic variants can be found in [2] and [4], and the nine visual “proofs without words” in [5] and [6] are also of interest.

Counting All Lattice Squares in a Grid of Unit Squares

Our goal in this second example is to prove that

[pic],

again by a counting argument As before, it is helpful to recast the identity into an equivalent form using binomial coefficients that is more suggestive of a combinatorial approach, namely

[pic]. (B)

The number of tilted and aligned lattice squares in an n ( n grid of unit squares is counted in two ways, so that identity (B) follows by equating the two counts.

Count B1. As shown in Figure 3, each tilted square is contained in a unique aligned bounding square (shown with dotted sides). For [pic], we know from our proof of (A) that there are k2 positions for the lower left corner of any bounding square with sides of length n + 1– k. This aligned square bounds an additional n – k tilted squares, so the total number of lattice squares in an n ( n grid —tilted and aligned—is [pic].

Count B2. This time let set S be defined by

[pic].

Any square in the n ( n grid is then described uniquely by a quadruple (a, b, c, d) from S in the following way. If 0 ( a ( b < c < d ( n, we let (a, b) locate the lower left corner of the bounding square, let c be the level touched by the inscribed tilted square on the left side of the bounding square, and d be the horizontal level of the upper side of the bounding square. When b < a < c < d ( n, we simply let (a, b, c, d) be the square (b, a, c, d) reflected over the main diagonal of the grid. Thus, all of the tilted squares are described when d ( n. Now suppose d = n + 1. Here we let (a, b, c, n + 1) correspond to the untilted lattice square with lower left corner at (a, b) and with c as the larger coordinate of the upper right corner of the square.

To determine |S|, once again we introduce an auxiliary set T, this time defined by

[pic].

There are [pic] ways to choose w and x, and then [pic] ways to choose y and z in such a way that w is not rechosen. Therefore, [pic]. Just as before, we will show that there is a one-to-three relation from S onto T. Given (a, b, c, d) from S, there will again be three cases depending on whether the lower left corner (a, b) of the bounding square is (1) above, (2) below, or (3) on the main diagonal of the grid (see Figure 4).

Case 1: a < b

Here a < b < c < d, and we map the quadruple (a, b, c, d) from S to the three quadruples (a, b, c, d), (a, c, b, d), and (a, d, b, c) in T. Notice that in each of these quadruples

(w, x, y, z), w, x, y, and z are distinct, and y > w.

Case 2: b < a

Now b < a < c < d, and we map the quadruple (a, b, c, d) from S to the three quadruples

(a, c, b, d), (a, d, b, c), and (c, d, a, b) in T. As with Case 1, w, x, y, and z are distinct but now y < w.

Case 3: a = b

Here a = b < c < d, and we map the quadruple (a, a, c, d) from S to the three quadruples (a, c, c, d), (c, d, a, d), and (a, d, c, d) in T. These are the quadruples (w, x, y, z) for which w, x, y, and z are not all distinct since either y or z is equal to x.

The three cases just described give a one-to-three correspondence from S onto the [pic] members of T. Thus, the total number of lattice squares in the grid, both tilted and aligned, is

[pic].

This proves (B).

The combinatorial proof of the sum of sums of squares just given meets the challenge set forth in [4]. It should also be observed that combinatorial reasoning may lead to alternative expressions that give the same count in a different form. For example, as described in Case 1 of Count B2, the [pic] four-tuples (a, b, c, d) with 0 ( a < b < c < d ( n + 1 describe the squares found within bounding squares with lower left corners at (a, b) above the main diagonal. Similarly, there are [pic] three-tuples (a, b, c) with

0 ( a < b < c ( n + 1 that describe the lattice squares whose bounding squares have their lower left corners on the main diagonal. Altogether, this gives [pic] squares in the grid, and proves that

[pic].

It is easy to check algebraically that this identity is equivalent to the more compact form of identity (B).

Another form of the identity is obtained by applying Brualdi’s Theorem 8.2.3 [3], this time giving

[pic].

A visual “proof without words” of identity B due to C. G. Wastun is in [6, p. 91].

References

1. A. T. Benjamin, J. J. Quinn, and C. Wurtz, Summing cubes by counting rectangles, College Math. J. 37 (2006) 387–389.

2. A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America, Washington DC, 2003.

3. R. A. Brualdi, Introductory Combinatorics, 4th ed., Pearson Prentice-Hall, Upper Saddle River NJ, 2004.

4. D. DeTemple, Combinatorial proofs via flagpole arrangements, College Math. J. 35 (2004) 129–133.

5. R. B. Nelsen, Proofs Without Words I, Mathematical Association of America, Washington DC, 1997.

6. --------------, Proofs Without Words II, Mathematical Association of America, Washington DC, 2000.

-----------------------

Figure 1. Counting lattice squares aligned to an n ( n grid.

n +1– k

0

0

n

n

k – 1

k – 1

[pic]

[pic]

[pic]

n

n

0

0

Figure 3. Counting tilted lattice squares.

n +1– k

0

0

n

n

k – 1

k – 1

[pic]

Figure 4. Lattice squares and their associated quadruples from S and T.

[pic]

[pic]

[pic]

0 1 2 3 4 5 6 7 8 9 10 n

[pic]

Figure 2. Every aligned square in the grid is associated with one triple from S and three triples from T.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download