Identities in the Multiplication Table
There are many patterns in the common multiplication table. Some are suggested by the applet below.
Just move the mouse over.
Discussion
Copyright © 1996-2008 Alexander Bogomolny
Identities in the Multiplication Table
The applet points to four identities:
| (1) | (1 + 2 + 3 + ... + n)2 = [n(n+1)/2]2 |
| (2) | 2n(1 + 2 + 3 + ... + n) - n2 = n3 |
| (3) | 12 + 22 + 32 + ... + n2 = n(n + 1)(2n + 1)/6 |
| (4) | n·1 + (n - 1)·2 + (n - 2)·3 + ... + 2·(n - 1) + 1·n = n(n + 1)(n + 2)/6 |
The sum of all entries in an n×n multiplication table equals [n(n+1)/2]2. Indeed, the sum of the entries in the first row is 1 + 2 + ... + n = n(n + 1)/2. Then grouping the entries by rows be get
| Row | | Sum |
|---|
| 1 | | 1 + 2 + ... + n = 1·n(n + 1)/2 |
| 2 | | 2 + 4 + ... + 2n = 2·n(n + 1)/2 |
| 3 | | 3 + 6 + ... + 3n = 3·n(n + 1)/2 |
| | | ... |
| n | | n + 2n + ... + n·n = n·n(n + 1)/2 |
| Total | | (1 + 2 + ... + n)·n(n + 1)/2 = [n(n+1)/2]2 |
This settles (1).
(2) arises as the sum of entries in the nth column and in the nth row, the diagonal term n2 being counted only once. The entries in both the nth row and the nth column add up to
| | n·(1 + 2 + ... + n) = n2(n + 1)/2. |
Together, but with the exclusion of the diagonal entry, we get
| | 2·n2(n + 1)/2 - n2 = (n3 + n2) - n2 = n3. |
As a bonus, a combination of (1) and (2) leads to the following curious identity:
| |
(1 + 2 + ... + n)2 = 13 + 23 + ... + n3
. |
(3) is the sum of the diagonal entries, i.e., the sum of the first n squares. The formula is well known and is easily proven by induction. Mathematical induction, however, though a powerful tool, is limited to the cases when the formula to be proven is known (or has been guessed) up front. But how does one get those formulas in the first place? Here is one possible approach based on the theory of generating functions.
Denote qn = 12 + 22 + 32 + ... + n2. Then obviously the sequence {qn} satisfies the recurrence relation
Multiply the relation by xn-1 and add up the first n:
| | Q(x)/x = Q(x) +  nn2xn-1, |
where Q(x) is the generating function of the sequence {qn}. This would be determined from
| (5) | Q(x)(1 - x)/x = nn2xn-1 |
if we could express the sum on the right in terms of x. Let's try,
| |
nn2xn
= nn(n + 1)xn-1 - nnxn-1
|
The sum nnxn-1 has been found to equal 1/(1 - x)2 as the formal derivative of the sum of the geometric series 1/(1 - x) = 1 + x + x2 + ... We shall apply the same idea to the series nn(n + 1)xn-1.
| |
|
nn(n + 1)xn-1 | = [1/(1 - x)]'' |
| | = [1/(1 - x)2]' |
| | = 2/(1 - x)3. |
|
From (5) then
| |
|
Q(x) | = x/(1 - x)·(2/(1 - x)3 - 1/(1 - x)2) |
| | = x/(1 - x)·(1 + x)/(1 - x)3 |
| | = x(1 + x)/(1 - x)4. |
|
We know that nC(n,k)xn = xk/(1-x)k+1, which implies
| |
|
[xn]Q(x) | = [xn]x/(1 - x)4 + [xn]x2/(1 - x)4 |
| | = C(n+2,3) + C(n+1,3) |
| | = (n + 2)(n + 1)n/6 + (n + 1)n(n - 1)/6 |
| | = n(n + 1)(2n + 1)/6. |
|
In (4), the coefficients are obtained by convolution of the terms of the plain sequence {n}. Convolutions arise when power series are multiplied term by term according to the definition. Let t0 = 0 and t1 = 0 and, for n = 2, 3, ...,, define tn = (n - 1)·1 + (n - 2)·2 + (n - 3)·3 + ... + 2·(n - 2) + 1·(n - 1). Introduce the generating function T(x) = ntnxn.
| |
|
T(x) | = (x + 2x2 + 3x3 + ...)·(x + 2x2 + 3x3 + ...) |
| | = x/(1 - x)2·x/(1 - x)2 |
| | = x2/(1 - x)4. |
|
Using the same identity as above,
| |
[xn]T(x) = [xn]x2/(1 - x)4 = C(n+1,3) = (n + 1)n(n - 1)/6. |
Thus tn = (n + 1)n(n - 1)/6, which corresponds to the sum of terms in the (n - 1)st diagonal.
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Euler's derivation of the binary representation
- Examples with series of figurate numbers
- Examples with finite sums with binomial coefficients
- Fast Power Indices and Coin Change
- Number of elements of various dimensions in a tesseract
- Straight Tromino on a Chessboard
- Ways To Count
Copyright © 1996-2008 Alexander Bogomolny
| 
