# Examples with series of figurate numbers

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

What if applet does not run? |

Just move the mouse over.

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

### Identities in the Multiplication Table

The applet points to four identities:

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

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 n^{th} column and in the n^{th} row, the diagonal term n^{2} 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^{2}(n + 1)/2.

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

2·n^{2}(n + 1)/2 - n^{2} = (n^{3} + n^{2}) - n^{2} = n^{3}.

As a bonus, a combination of (1) and (2) leads to the following curious identity, known as *Nicomachus' theorem*

(1 + 2 + ... + n)^{2} = 1^{3} + 2^{3} + ... + n^{3}.

(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} + 2^{2} + 3^{2} + ... + n^{2}. Then obviously the sequence {q_{n}} satisfies the recurrence relation

q_{n} = q_{n-1} + n^{2}, q_{0} = 0.

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

Q(x)/x = Q(x) + ∑_{n}n^{2}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 = ∑_{n}n^{2}x^{n-1} |

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

∑_{n}n^{2}x^{n}
= ∑_{n}n(n + 1)x^{n-1} - ∑_{n}nx^{n-1}

The sum ∑_{n}nx^{n-1} has been found to equal 1/(1 - x)^{2} as the formal derivative of the sum of the geometric series ^{2} + ..._{n}n(n + 1)x^{n-1}.

∑_{n}n(n + 1)x^{n-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 ∑_{n}C(n,k)x^{n} = x^{k}/(1-x)^{k+1}, which implies

[x^{n}]Q(x) | = [x^{n}]x/(1 - x)^{4} + [x^{n}]x^{2}/(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 _{0} = 0_{1} = 0_{n} = (n - 1)·1 + (n - 2)·2 + (n - 3)·3 + ... + 2·(n - 2) + 1·(n - 1)_{n}t_{n}x^{n}.

T(x) | = (x + 2x^{2} + 3x^{3} + ...)·(x + 2x^{2} + 3x^{3} + ...) |

= x/(1 - x)^{2}·x/(1 - x)^{2} | |

= x^{2}/(1 - x)^{4}. |

Using the same identity as above,

[x^{n}]T(x) = [x^{n}]x^{2}/(1 - x)^{4} = 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

- Generating Functions
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Examples with series of figurate numbers
- Euler's derivation of the binary representation
- 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
- Probability Generating Functions
- Finite Sums of Terms 2^(n-i) i^2
- Sylvester's Problem, a Second Look
- Generating Functions from Recurrences
- Binet's Formula via Generating Functions
- Number of Trials to First Success
- Another Binomial Identity with Proofs

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

62642291 |