Richard Guy's Number Walls
A "number wall", as described in the 1995 book The Book of Numbers by Conway and Guy [1], is a way to derive a formula for certain sequences that have a recurrence relation, including linear combinations of previous terms (as with the Fibonacci numbers, Sloane's A0045) or convolutions (as with the Catalan numbers, A0108).
The number wall is a grid of rows and columns, like a spreadsheet. Fill the first row with 1's and put the sequence of interest in the second row:
|
Richard Guy gives the following formula for the relationship between the numbers in various cells of the grid:
C2=RL+AB
C represents a number in a cell of the grid, and A,B,R,L represent the numbers above, below, to the left, and to the right respectively.
As discussed below, Michael Somos uses a different version of this formula:
C2=RL-AB
The Somos version works better for the Catalan numbers, simply because it gives positive numbers in all cells (except in a lower-left section which we do not need and will leave unfilled).
So, we fill the next row by solving the formula C2=RL-AB one cell at a time. Since we're filling in the row "below", we want B given A, L, C, and R so we express the formula as B=(RL-C2)/A.
If the sequence has a recurrence of the type that Richard Guy's method can handle, then all the numbers will be integers. In this example, we get ?, 1, 1, 3, 14, 84, 594, 4719, 40898, ... We continue in the same way for the next row: ?, ?, 1, 1, 4, 30, 330, 4719, 81796, ... and likewise for subsequent rows.
When as many numbers are filled in as possible (and here adding a few more terms of the initial rows to get a bigger triangle), we have this:
|
At this point we would look for a pattern and we notice all 1's on the two diagonals shown in boldface. Making an hypothesis that this pattern continues, we can fill in another 1 on the 7th row. Then we transform the above formula into R=(AB+C2)/L, and use it to solve up the ascending diagonal, adding the numbers here shown in italics:
|
and indeed we get the next of the Catalan numbers, 58786.
To get the next term after that, we notice that there is an ascending sequence of natural numbers in the diagonal just to the right of the two diagonals containing 1's, so we guess that the number under 91 must be 7. This pattern works, and we now have enough of a pattern to continue generating Catalan numbers as far as we like.
Other "number walls" are computed in a similar way. One might try this method starting with any of these sequences in the 2nd row:
- the powers of 2
- the positive (and nonzero) Fibonacci numbers
- positive values of 3n-2n (sequence A001047)
and each time speculate about what appears in the 3rd row and why.
Note that when there are 0's in the grid one must use extra numbers from an expanded neighbourhood around the 0's. Some details and examples of this are in the Conway and Guy book. A much more detailed presentation is given in the Mathologer video Secrets of the lost number walls. In addition to methods of solving zeros, several properties related to 0's are discussed (such as the fact that 0's always occur in square blocks), and then this is generalised to the properties of blocks of cells that are equal to 0 modulo some prime number (e.g. multiples of 5 — you can see a 2×2 block in the Catalan wall above). He also discusses the remarkable fact that number walls starting with an integer sequence can always be filled in entirely with integers, which comes from the related fact that elements of number walls are determinants of Hankel or Toeplitz matrices.
In 2000 Michael Somos discussed number walls in the presentation Number Walls in Combinatorics. Near the beginning he refers to "the fundamental equation" as the following:
x = y-y2 = z-z3 (1)
From this he derives an infinite polynomial in x that can be used for y in the fundamental equation. We start with just the part of (1) that has the x and y terms:
y = x + y2 (2)
and we postulate that the right hand side can be expressed as a polynomial in x:
y = x + ax2 + bx3 + cx4 + ... (3)
The unknown coefficients a, b, c, ... can be inferred by repeating a process of squaring the existing known part of the polynomial and leaving the unknown part as simply "...", like so:
First, substitute the right side of (3) for y in the right side of (2), to get:
y = x + y2 = x + (x+...)2
Expand the part in parentheses. The coefficient of x2 must be 1, and the higher coefficients have letters: 2ax3, (a2+2b)x4, and so on. But we don't need to worry about those, instead just take the part we know and use an ellipsis "..." for the rest, and (3) becomes:
y = x + x2 + ...
Now substitute the right side of this for y in (2), to get:
y = x + (x+x2+...)2
We can again expand the parenthesised part, and we get the x3 term explicitly:
y = x + x2 + 2x3 + ...
And so we continue, each time getting one more term with an explicit number:
y = x + (x+x2+2x3+...)2
= x + x2 + 2x3 + 5x4 + ...
= x + (x+x2+2x3+5x4+...)2
= x + x2 + 2x3 + 5x4 + 14x5 + ...
= (etc.)
This process generates the Catalan numbers as the coefficients.
Another way to say the same thing is that we start with (2) and (3) above, then substitute the second into the first with all the unknowns in place:
y = x + (x+ax2+bx3+cx4+...)2 (4)
then expand all the terms to get this:
y = x + x2 + 2ax3 + (a2+2b)x4 + (2c+2ab)x5 + ... (5)
and then, using the fact that this must be equal to the original x + ax2 + bx3 + cx4 + ..., work out the coefficients one at a time: Since the x2 in (5) must be the same as the ax2 in (3) we know a=1, then we can solve bx3 = 2ax3 to get b=2, and so on.
In pari-gp this process is automated in a very direct and obvious way:
my(y=O(x)); for(n=1,8,y=x+y^2; print(y))
In Mathematica the iteration can be done by the NestList operator using this much-less-obvious code (the "// Column" part just makes it show one iteration per line of output):
NestList[x + #^2 &, O[x], 8] // Column
In the code, "O(x)" and "O[x]" both represent Bachmann-Landau Big O notation, implemented directly in pari-gp and Mathematica.
y As a Series in z
Somos then expands "y as a series in z", which uses the part of (1) that has y and z, i.e. y-y2 = z-z3. As above, we start by putting the single y on the left and the rest on the right, and expressing as a polynomial in z by expressing the y2 as a polynomial in z with unknown coefficients:
y = z - z3 + y2 (6)
y2 = z + az2 + bz3 + cz4 + ... (7)
Working out the coefficients one at a time goes similarly to the previous example, except that we have an extra step of subtracting 1 from the z3 coefficient to account for the "-z3" in (6). As above, at each step when we are showing the "y2" term as a polynomial squared, we show that part in boldface. At each step we expand the y2 polynomial to as many terms as we can determinine explicitly. After the first couple steps the expansion includes a 2z3 term, so we take an additional step to combine this with the "-z3" in the original formula.
y = z - z3 + (z+...)2
= z - z3 + z2 + ...
= z + z2 + ...
= z - z3 + (z+z2+...)2
= z - z3 + z2 + 2z3 + ...
= z + z2 + (2-1)z3 + ...
= z - z3 + (z+z2+z3+...)2
= z - z3 + z2 + 2z3 + 3z4 + ...
= z + z2 + (2-1)z3 + 3z4 + ...
= z - z3 + (z+z2+z3+3z4+...)2
= z - z3 + z2 + 2z3 + 3z4 + 8z5 + ...
= z + z2 + (2-1)z3 + 3z4 + 8z5 + ...
= (etc.)
The coefficients are: 1, 1, 1, 3, 8, 23, 68, 207, ... (Sloane's sequence A25262).
The pari-gp code for this is just as simple as before:
my(y=O(z)); for(n=1,8,y=z-z^3+y^2; print(y))
Other Similar Expansions
Performing a similar expansion for z as a series in x:
my(z=O(x)); for(n=1,8,z=x+z^3; print(z))
yields x + x3 + 3x5 + 12x7 + 55x9 + 273x11 + 1428x13 + 7752x15 + ... and the sequence 1, 0, 1, 0, 3, 0, 12, 0, 55, 0, 273, 0, 1428, ... which is A1764 in the OEIS, related to ternary trees in the same way that the Catalan numbers are related to binary trees.
The last expansion, not in Somos' 2000 talk, is to give z in terms of y: The equation (1) becomes z = y - y2 + z3 and the pari-gp code:
my(z=O(y)); for(n=1,5,z=y-y^2+z^3; print(z))
gives y - y2 + y3 - 3y4 + 6y5 - 16y6 + 42y7 - 114y8 + 322y9 - 918y10 + ... The coefficients with the signs removed: 1, 1, 1, 3, 6, 16, 42, 114, 322, 918, 2673, ... is A19497 in the OEIS — another sequence related to ternary trees. This same sequence (with all positive signs) is achieved with the equation z=y+y2+z3, i.e. just changing the sign of y2 in the above equation.
References
[1] John H. Conway and Richard Guy. The book of numbers. Springer-Verlag New York, 1995. ISBN 0-387-97993-X.
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Oct 19.
s.30