Tuesday, December 22, 2009

the Lucas Number Triangle

Polygonal numbers have been a recurring topic on this blog (starting with the first post) and although they might eventually exhaust me, I've realized that I'll never exhaust their recreational possibilities.

One interesting way to look at polygonal numbers is to arrange them into number triangles - for a particular \(k \geq 3 \) you can do this by arranging the k-polygonal numbers in diagonals by dimension. If you do this with the triangular numbers, you get Pascal's Triangle. Said another way, the diagonals of Pascal's triangle list  the various dimensional extensions of triangular numbers: the 3rd diagonal gives the usual 'triangular numbers', the 4th diagonal gives the tetrahedrals (now to be referred to as the 'days of Christmas numbers'), the 5th diagonal gives the triangulo-triangular numbers, etc. Each diagonal lists the finite differences of the diagonal below it, so the second diagonal of Pascal's triangle gives what we could call the 'one dimensional triangulars' or the Naturals, and the first diagonal gives us 'zero dimensional triangulars' - the constant sequence of 1s.

The symmetry of Pascal's Triangle allows you to see the various dimensions of the triangular numbers in both the diagonals that slope downward from left to right, and those that slope downward from right to left. However, when you do the same sort of construction with \(k \geq 4 \) you loose this symmetry, and have to pick a direction. When I tried this (described here and here), I chose to make my generalized k-polygonal Pascal Triangles 'left handed', so that the k-polygonal numbers appear in the diagonals sloping downward from right to left. The diagrams below show the left-handed triangles for the square (k = 4) and pentagonal numbers (k = 5).

Using \( \left[\begin{array}{c}n\\r\end{array}\right]^{\mathcal{L}}_{k} \) to denote the entry in the nth row of the rth diagonal column of the left-handed k-polygonal number triangle, we can express this construction recursively in a way that is very similar to the usual Pascal Triangle definition:

We can express the terms directly using the binomial coefficients:

Instead of making the triangles left-handed, we could instead make them right-handed like these:

Where now all the k-polygonal numbers appear as diagonals sloping downward from left to right. These are almost mirror images of the left-handed variety, and to be honest, I am not sure what the correct value is for the topmost entry. In these formulations, for both the left-handed and right-handed variety, the topmost entry is determined by the value in the far-right column.

Using \( \left[\begin{array}{c}n\\r\end{array}\right]^{\mathcal{R}}_{k} \) to denote the entry in the nth row of the rth diagonal column of the right-handed k-polygonal number triangle, we can express the construction recursively:

And, just as with the left-handed variety, we can express the terms using binomial coefficients:

For the case where k=3, it is easy to see that both our left-handed and right-handed k-polygonal Pascal Triangles are equal to the usual Pascal Triangle.

It turns out that for the right-handed k = 4 case ('square' polygonals) gives a well-known number triangle called the Lucas Number Triangle.

In the Lucas Number Triangle you find the square numbers, the square-based pyrimidal numbers, and all of the higher-dimensional versions of the same, just as you find the triangular, pyrimidal, and higher-triangular numbers in Pascal's Triangle

In the same way that you can find the Fibonacci numbers by summing left-to-right upward sloping diagonals in the regular Pascal's Triangle, you can find Lucas numbers (see also Wikipedia) by summing  left-to-right upward sloping diagonals in the Lucas Number Triangle. Lucas numbers are a generalization of the Fibonacci sequence - the Fibonacci sequence starts with the numbers \( f_0 = 0 \), \( f_1=1 \), and proceeds according to the rule \( f_n = f_{n-1} + f_{n-2} \); the Lucas sequence starts with the numbers \( f_0 = 2 \), \( f_1=1\), and follows the same generating rule as the Fibonacci sequence.

Just as the entries in Pascal's Triangle can be interpreted as coefficients in the expansion of the binomial \( (a+b)^n \), the entries in the Lucas triangle can be seen to be coefficients in the expansion of the binomial \( (a+2b)(a+b)^{n-1} \) for \( n \geq 1 \).

In general, right handed k-polygonal Triangles give generalized "Gibonacci Numbers" - number sequences that follow the usual Fibonacci rule but with different first terms, in this case, \( G_0=k-2 \) and \( G_1=1 \). These Gibbonacci Number Triangles have entries whose rows give the coefficients of \( (a+ (k-2)b)(a+b)^{n-1} \) for \( n \geq 1\).

A nice overview of the Lucas and Gibonacci Triangles and an interesting combinatorial interpretation of their entries is given in Arthur Benjamin's The Lucas Triangle Recounted.