Examples with series of figurate numbers

There are many patterns in the common multiplication table. Some are suggested by the applet below.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

Just move the mouse over.

Discussion

Identities in the Multiplication Table

The applet points to four identities:

(1)	(1 + 2 + 3 + ... + n)² = [n(n+1)/2]²
(2)	2n(1 + 2 + 3 + ... + n) - n² = n³
(3)	1² + 2² + 3² + ... + n² = 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]². 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]²

This settles (1).

(2) arises as the sum of entries in the n^th column and in the n^th row, the diagonal term n² being counted only once. The entries in both the n^th row and the n^th column add up to

n·(1 + 2 + ... + n) = n²(n + 1)/2.

Together, but with the exclusion of the diagonal entry, we get

2·n²(n + 1)/2 - n² = (n³ + n²) - n² = n³.

As a bonus, a combination of (1) and (2) leads to the following curious identity:

(1 + 2 + ... + n)² = 1³ + 2³ + ... + n³.

(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 q_n = 1² + 2² + 3² + ... + n². Then obviously the sequence {q_n} satisfies the recurrence relation

q_n = q_n-1 + n², q₀ = 0.

Multiply the relation by x^n-1 and add up the first n:

Q(x)/x = Q(x) + ∑_nn²x^n-1,

where Q(x) is the generating function of the sequence {q_n}. This would be determined from

(5)	Q(x)(1 - x)/x = ∑_nn²x^n-1

if we could express the sum on the right in terms of x. Let's try,

∑_nn²xⁿ = ∑_nn(n + 1)x^n-1 - ∑_nnx^n-1

The sum ∑_nnx^n-1 has been found to equal 1/(1 - x)² as the formal derivative of the sum of the geometric series 1/(1 - x) = 1 + x + x² + ... We shall apply the same idea to the series ∑_nn(n + 1)x^n-1.

∑_nn(n + 1)x^n-1	= [1/(1 - x)]''
	= [1/(1 - x)²]'
	= 2/(1 - x)³.

From (5) then

Q(x)	= x/(1 - x)·(2/(1 - x)³ - 1/(1 - x)²)
	= x/(1 - x)·(1 + x)/(1 - x)³
	= x(1 + x)/(1 - x)⁴.

We know that ∑_nC(n,k)xⁿ = x^k/(1-x)^k+1, which implies

[xⁿ]Q(x)	= [xⁿ]x/(1 - x)⁴ + [xⁿ]x²/(1 - x)⁴
	= 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 t₀ = 0 and t₁ = 0 and, for n = 2, 3, ...,, define t_n = (n - 1)·1 + (n - 2)·2 + (n - 3)·3 + ... + 2·(n - 2) + 1·(n - 1). Introduce the generating function T(x) = ∑_nt_nxⁿ.

T(x)	= (x + 2x² + 3x³ + ...)·(x + 2x² + 3x³ + ...)
	= x/(1 - x)²·x/(1 - x)²
	= x²/(1 - x)⁴.

Using the same identity as above,

[xⁿ]T(x) = [xⁿ]x²/(1 - x)⁴ = C(n+1,3) = (n + 1)n(n - 1)/6.

Thus t_n = (n + 1)n(n - 1)/6, which corresponds to the sum of terms in the (n - 1)^st diagonal.

Generating Functions

40618003