This file was last updated: 11/17/2018 1:33:40 AM
Experimental Mathematics on Wisteria Tables
Abstract
"Experimental mathematics is an approach to mathematics in
which computation is used to investigate mathematical objects and
to identify properties and patterns." Eric W. Weisstein, quoted
in en.wikipedia.org/wiki/Experimental_mathematics
The Online Encyclopedia of Integer Sequences (OEIS) contains
over 300,000 integer sequences. To browse it is to rekindle a
childhood wonder at how fascinating mathematics can be. A math
problem provided by Marist College Prof. Joseph Kirtland a year
ago led me to arrange 30 of the known OEIS sequences into a table,
which was published at OEIS.org/A299741. I found multiple distinct
algorithms which generate the table. The wisteria name is meant
to recall the interconnectedness of the plant.
------------------------
Here is Table 5_14_18 = OEIS.org/A299741, unbounded below and to the right.
i\j| 0 1 2 3 4 5 6 7 8 9
---+-----------------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2
1| 2 3 7 _18_ 47 123 322 843 2207 5778
2| 2 4 _14_ 52 194 724 2702 10084 37634 140452
3| 2 _5_ 23 110 527 2525 12098 57965 277727 1330670
4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
5| 2 7 47 322 2207 15127 103682 710647 4870847 33385282
6| 2 8 62 488 3842 30248 238142 1874888 14760962 116212808
7| 2 9 79 702 6239 55449 492802 4379769 38925119 345946302
8| 2 10 98 970 9602 95050 940898 9313930 92198402 912670090
9| 2 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
Named for the middle values of the fifth upward diagonal.
It first appeared on OEIS on Jan 24, 2018, at oeis.org/A298675
and shortly later on Feb 18, 2018, at oeis.org/A299741.
The table is generated by three very distinct algorithms: A0,
A1, and A2 (to be defined) and possibly by four other algorithms
A3, A4, A5, and A6 (to be described).
The experimental mathematics in this work occurs in the
creation of examples. See, in particular, Section D. But, to
expand the meaning of the phrase, also in the search, via the
web, for examples. In the latter endeavor OEIS has been very,
very helpful.
This material is meant to be readable and self-contained. It
is aimed for a freshman or sophomore undergraduate mathematics
major.
========================================================== p. 2
Outline of tonight's talk.
Section A. History of developing Table 5_14_18.
Starting from a simple problem from Dr. Joseph Kirtland a year ago.
This is the hardest part of the talk.
Prove that if x + 1/x is an integer, then so are all these
values: x^2 + 1/x^2, x^3 + 1/x^3, x^4 + 1/x^4,,,.
1. Begin with computing the values r^n + 1/r^n, n=0,1,2,...,
where r is a root of x + 1/x = k, k=1,2,3,.... Create Table
5_14_18. Call this algorithm A2. Yes, this is confusing.
2. Discover recurrence relations among the elements of each
row. Realize that they also generate Table 5_14_18. Call this
algorithm A1. Forget about A2.
3. Look for polynomials creating the columns. They must
exist. Call them rule A_ ("A blank").
4. Discover that the polynomials are embedded in the (1,2)
Pascal triangle.
5. See that the polynomials are defined recursively. Call this
algorithm A0. Same polynomials. Deeper understanding of their
structure. Forget about A_.
6. See that the definitions of A0 and A1 are syntactically
identical, but semantically distinct.
So far everything has been done with just Table 5_14_18 in mind.
Many more examples of these behaviors can be found at More tables
Many more examples of these behaviors can be found at Table 2_4_5
Section B. Detour: OEIS - Online Encyclopedia of Integer Sequences (OEIS)
What it offers, how to use it, how much fun it can be.
How helpful it can be in seeking patterns among numbers.
Section C. Detour: scavenger hunt in OEIS for more algorithms
to generate Table 5_14_18.
at least one: A3.
maybe three more: A4, A5, A6
Section D. Question. Are there other tables which are
generated by rules of type A0?
Answer: Yes, every (a,b) Pascal triangle generates at least
three such tables ((1) using all the diagonals; (2) using the
even diagonals; and (3) using the odd diagonals).
View 30 examples at More tables
Question. Are there other wisteria tables which are not
associated with Pascal triangles? Answer: yes.
Section E. Conclusion.
Definition. A table T of integers is wisterian if there exists
a sequence A0 of recursively defined polynomials p[i](n) such
that polynomial i generates column i of table T when evaluated
for n = 0,1,2,....
Conjecture. For every wisteria table T with generating
polynomials A0 there is a sequence of recursion relations A1 such
that the i-th recursion relation defines the integers in row i of
T. Further, A0 and A1 are syntactically identical (though
semantically distinct since one defines polynomials and the other
defines recurrence relations).
========================================================== p. 3
Background info
------------------------------------------------
The roots r1 and r2 of the quadratic equation
a * x^2 + b * x + c = 0
are
-b + sqrt(b^2 - 4*a*c)
r1 = ------------------------
2 * a
and
-b - sqrt(b^2 - 4*a*c)
r2 = ------------------------
2 * a
------------------------------------------------ p. 4
The best known example of a recurrence relations is the
Fibonacci sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
which is defined by
a(0) = 1; a(1) = 1; a(i) = a(i-1) + a(i-2), i>1.
------------------------------------------------ p. 5
Let polynomial p(n) = a * n^3 + b * n^2 + c * n + d.
We want to find a,b,c,d such that:
p(0) = u
p(1) = v
p(2) = x
p(3) = y
So solve these simultaneous equations for a,b,c,d:
p(0) = 0 * a + 0 * b + 0 * c + d = u
p(1) = 1 * a + 1 * b + 1 * c + d = v
p(2) = 8 * a + 4 * b + 2 * c + d = x
p(3) = 27 * a + 9 * b + 3 * c + d = y
------------------------------------------------ p. 6
Pascal's triangle is
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Each number is the sum of the two numbers above it.
------------------------------------------------ p. 7
The (1,2) Pascal triangle is:
1 2
1 3 2
1 4 5 2
1 5 9 7 2
Each number is the sum of the two numbers above it.
AKA Lucas triangle, AKA Vieta's array (oeis.org/A029635)
------------------------------------------------ p. 8
The (a,b) Pascal triangle is:
a b
a a+b b
a 2a+b a+2b b
a 3a+b 3a+3b a+3b b
a 4a+b 6a+4b 4a+6b a+4b b
==========================================================
========================================================== p. 9
Section A. History of developing Table 5_14_18
Algorithm A2
Last September Dr. Joseph Kirtland showed me this problem:
Prove that if x + 1/x is an integer >= 2, then x^n + 1/x^n is
also an integer. (^ denotes exponentiation).
I could not believe it. I chose instead to look for a
counterexample.
I decided to try:
Case 1. Solve x + 1/x = 1
Case 2. Solve x + 1/x = 2
Case 3. Solve x + 1/x = 3
Case 4. Solve x + 1/x = 4
Case 5. Solve x + 1/x = 5
Case 6. Solve x + 1/x = 6, etc.
and for each case to compute the values
x + 1/x, x^2 + 1/x^2, x^3 + 1/x^3, . . .
------------------------------------------------ p. 10
Case 1. If x + 1/x = 1
then x^2 - x + 1 = 0.
The roots are:
1 + sqrt(1 - 4)
r1 = ---------------.
2
1 - sqrt(1 - 4)
r2 = ---------------.
2
This gets messy, so ignore Case 1.
--------------
Case 2. If x + 1/x = 2, then x^2 - 2*x + 1 = 0.
The roots are:
2 + sqrt(4 - 4)
r1 = --------------- = 1
2
2 - sqrt(4 - 4)
r2 = --------------- = 1
2
so r1^n + 1/r1^n = 2, for n >= 0, and
r2^n + 1/r2^n = 2, for n >= 0.
------------------------------------------------ p. 11
Case 3. If x + 1/x = 3, then x^2 - 3*x + 1 = 0.
The roots are:
3 + sqrt(9 - 4) 3 + sqrt(5)
r1 = ----------------- = ------------- = 2.618034
2 2
3 - sqrt(9 - 4) 3 - sqrt(5)
r2 = ----------------- = ------------- = 0.381966
2 2
Using the value 2.618034 yields
n 0 1 2 3 4 5 6 7 8
x^n 1 2.618034 6.854102 17.944212 46.978775 122.99187 321.9969 842.99884 2206.9996
1/x^n 1 0.381966 0.145898 0.055728 0.021286 0.00813 0.0031 0.00118 0.0004
sum 2 3.000000 7.000000 17.999940 47.000061 123.00000 322.0000 843.00002 2207.0000
2 3 7 18 47 123 322 843 2207
Using the value 0.381966 yields
n 0 1 2 3 4 5 6 7 8
x^n 1 0.381966 0.145898 0.055728 0.021286 0.00813 0.0031 0.00118 0.0004
1/x^n 1 2.618034 6.854102 17.944212 46.978775 122.99187 321.9969 842.99884 2206.9996
sum 2 3.000000 7.000000 17.999940 47.000061 123.00000 322.0000 843.00002 2207.0000
2 3 7 18 47 123 322 843 2207
------------------------------------------------ p. 12
One can look at the equation x^n +1/x^n = k and observe that it is
obvious that if r is a root of the equation, then so is 1/r. Or one
can do the algebra.
Theorem. Let r1 and r2 be the roots of the equation
x^2 - k*x + 1 = 0. Then r1 = 1/r2.
Proof. We know
k + sqrt(k^2 - 4) k - sqrt(k^2 - 4)
r1 = ------------------- and r2 = -------------------
2 2
k + sqrt(k^2 - 4) k - sqrt(k^2 - 4)
r1 * r2 = ------------------- * -------------------
2 2
k^2 - (sqrt((k^2 - 4))^2
= --------------------------
4
k^2 - k^2 + 4 4
= --------------- = --- = 1
4 4
------------------------------------------------ p. 13
Case 4. If x + 1/x = 4, then x^2 - 4*x + 1 = 0.
The roots are:
4 + sqrt(16 - 4)
r1 = ------------------ = 2 + sqrt(3) = 3.7320508
2
4 - sqrt(16 - 4)
r2 = ------------------ = 2 - sqrt(3) = 0.267949
2
n 0 1 2 3 4 5 6 7
x^n 1 3.7320508 13.928203 51.980762 193.99484 723.99967 2701.9996 10084.000
1/x^n 1 0.2679492 0.0717968 0.0192319 0.00515 0.00139 0.0003 0.000
sum 2 4.000000 14.00000 52.00000 193.99999 723.00106 2701.9999 10084.000
2 4 14 52 194 724 2702 10084
-------------------------------------------------
Case 5. r1 = ( 5 + sqrt(21) ) / 2 = 4.7912818
2 5 23 110 527 2525 12098
-------------------------------------------------
Case 6. r1 = ( 6 + sqrt(32) ) / 2 = 5.8284277
2 6 34 198 1154 6726 39202
========================================================== p. 14
These efforts lead to:
Table 5_14_18.
i\j| 0 1 2 3 4 5 6 7 8 9
---+-----------------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2
1| 2 3 7 18 47 123 322 843 2207 5778
2| 2 4 14 52 194 724 2702 10084 37634 140452
3| 2 5 23 110 527 2525 12098 57965 277727 1330670
4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
5| 2 7 47 322 2207 15127 103682 710647 4870847 33385282
6| 2 8 62 488 3842 30248 238142 1874888 14760962 116212808
7| 2 9 79 702 6239 55449 492802 4379769 38925119 345946302
8| 2 10 98 970 9602 95050 940898 9313930 92198402 912670090
9| 2 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
Call the algorithm which led to the creation of this table A2.
========================================================== p. 15
A digression on naming tables
Conceivably "Table 5_14_18" could be too short. If so, then
call this table Table 5_14_18_23_52_110. Named for the values at
(3,1), (2,2), (1,3), (3,2), (2,3), (3,3).
i\j| 0 1 2 3 4 5 6 7 8 9
---+-----------------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2
1| 2 3 7 _18_ 47 123 322 843 2207 5778
2| 2 4 _14_ _52_ 194 724 2702 10084 37634 140452
3| 2 _5__23__110_ 527 2525 12098 57965 277727 1330670
4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
5| 2 7 47 322 2207 15127 103682 710647 4870847 33385282
6| 2 8 62 488 3842 30248 238142 1874888 14760962 116212808
7| 2 9 79 702 6239 55449 492802 4379769 38925119 345946302
8| 2 10 98 970 9602 95050 940898 9313930 92198402 912670090
9| 2 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
The trouble with this convention is that, if you somehow compute this table
i\j| 0 1 2 3 4 5 6 7 8
---+---------------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2
1| 3 7 18 _47_ 123 322 843 2207 5778
2| 4 14 _52_ 194 724 2702 10084 37634 140452
3| 5 _23_ 110 527 2525 12098 57965 277727 1330670
4| 6 34 198 1154 6726 39202 228486 1331714 7761798
5| 7 47 322 2207 15127 103682 710647 4870847 33385282
6| 8 62 488 3842 30248 238142 1874888 14760962 116212808
7| 9 79 702 6239 55449 492802 4379769 38925119 345946302
8| 10 98 970 9602 95050 940898 9313930 92198402 912670090
9| 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
you think its name is Table 23_52_47, but then you see that the tables
are the same, except for column 0 being omitted from the second.
I am not sure how to name tables.
========================================================== p. 16
Algorithm A1
As I created each row, I looked it up on OEIS.
There I found each row was defined as a recurrence relation.
a(0) = 2; a(1) = 2; a(n) = 2 * a(n-1) - a(n-2), n >= 2.
2 2 2 2 2 2 2 2 2
a(0) = 2; a(1) = 3; a(n) = 3 * a(n-1) - a(n-2), n >= 2.
2 3 7 18 47 123 322 843 2207
a(0) = 2; a(1) = 4; a(n) = 4 * a(n-1) - a(n-2), n >= 2.
2 4 14 52 194 724 2702 10084 37634
which generalizes to
a(i,0) = 2, i >= 0.
a(i,1) = i + 2, i >= 0.
a(i,j) = (i + 2) * a(i,j-1) - a(i,j-2) for i >= 0, j >= 2.
Call this algorithm A1.
i\j | 0 1 2 3 4 5 6 7 8 9
----+-----------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2
1| 2 3 7 18 47 123 322 843 2207 5778
2| 2 4 14 52 194 724 2702 10084 37634 140452
3| 2 5 23 110 527 2525 12098 57965 277727 1330670
4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
Theorem. Algorithms A1 and A2 generate the same table.
Proof. (by Dr. Joseph Kirtland). See Proof_A1_is_A2
To me it is just astonishing that two such very different
algorithms generate exactly the same numbers.
========================================================== p. 17
Algorithm A0
I noticed that the elements of column 1 differed by zero, the
elements of column 1 differed by i, the elements of column 2
differed by 5, 7, 9, 11, .... The natural question was:
What structure exists in the columns of Table 5_14_18? We know
that for any sequence of numbers, a0, a1, a2, ..., there is a
polynomial p(n) such that p(0)=a0, p(1)=a1, p(2)=a2, ....
Table 5_14_18.
i\j| 0 1 2 3 4 5 6 7 8 9
---+-----------------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2
1| 2 3 7 18 47 123 322 843 2207 5778
2| 2 4 14 52 194 724 2702 10084 37634 140452
3| 2 5 23 110 527 2525 12098 57965 277727 1330670
4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
5| 2 7 47 322 2207 15127 103682 710647 4870847 33385282
6| 2 8 62 488 3842 30248 238142 1874888 14760962 116212808
7| 2 9 79 702 6239 55449 492802 4379769 38925119 345946302
8| 2 10 98 970 9602 95050 940898 9313930 92198402 912670090
9| 2 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
I took successive differences for the values in each column.
The results were:
i\j| 0 1 i\j| 0 1 2 i\j| 0 1 2 3 i\j| 0 1 2 3 4 i\j| 0 1 2 3 4 5
---+---- ---+------- ---+----------- ---+---------------- ---+-------------------------
0| 2 0 0| 2 1 0 0| 2 5 2 0 0| 2 16 18 6 0 0| 2 45 102 84 24 0
1| 2 0 1| 3 1 0 1| 7 7 2 0 1| 18 34 24 6 0 1| 47 147 186 108 24 0
2| 2 0 2| 4 1 0 2| 14 9 2 0 2| 52 58 30 6 0 2| 194 333 294 132 24 0
3| 2 0 3| 5 1 0 3| 23 11 2 0 3| 110 88 36 6 0 3| 527 627 426 156 24 0
4| 2 0 4| 6 1 0 4| 34 13 2 0 4| 198 124 42 6 0 4| 1154 1053 582 180 24 0
5| 2 0 5| 7 1 0 5| 47 15 2 0 5| 322 166 48 6 0 5| 2207 1635 762 204 24 0
6| 2 0 6| 8 1 0 6| 62 17 2 0 6| 488 214 54 6 0 6| 3842 2397 966 228 0 0
7| 2 0 7| 9 1 0 7| 79 19 2 0 7| 702 268 60 0 0 7| 6239 3363 1194 0 0 0
8| 2 0 8| 10 1 0 8| 98 21 0 0 8| 970 328 0 0 0 8| 9602 4557 0 0 0 0
9| 2 0 9| 11 0 0 9| 119 0 0 0 9| 1298 0 0 0 0 9| 14159 0 0 0 0 0
i\j| 0 1 2 3 4 5 6 i\j| 0 1 2 3 4 5 6 7
---+----------------------------------- ---+----------------------------------------------
0| 2 121 480 720 480 120 0 0| 2 320 2060 4956 5736 3240 720 0
1| 123 601 1200 1200 600 120 0 1| 322 2380 7016 10692 8976 3960 720 0
2| 724 1801 2400 1800 720 120 0 2| 2702 9396 17708 19668 12936 4680 720 0
3| 2525 4201 4200 2520 840 120 0 3| 12098 27104 37376 32604 17616 5400 720 0
4| 6726 8401 6720 3360 960 120 0 4| 39202 64480 69980 50220 23016 6120 0 0
5| 15127 15121 10080 4320 1080 0 0 5| 103682 134460 120200 73236 29136 0 0 0
6| 30248 25201 14400 5400 0 0 0 6| 238142 254660 193436 102372 0 0 0 0
7| 55449 39601 19800 0 0 0 0 7| 492802 448096 295808 0 0 0 0 0
8| 95050 59401 0 0 0 0 0 8| 940898 743904 0 0 0 0 0 0
9| 154451 0 0 0 0 0 0 9| 1684802 0 0 0 0 0 0 0
This indicates each column is generated by a well-behaved polynomial.
========================================================== p. 18
We want to find polynomials such that
polynomial p[0](n) generates column 0,
polynomial p[1](n) generates column 1,
polynomial p[2](n) generates column 2,
polynomial p[3](n) generates column 3, etc.
where [i] shows what would normally be written as a subscript.
It is clear that
p[0](n) = 2, n >= 0.
p[1](n) = n + 2, n >= 0.
p[2](n) = n^2 + 4 * n + 2.
p[2](0) = 0^2 + 4 * 0 + 2 = 2
p[2](1) = 1^2 + 4 * 1 + 2 = 7
p[2](2) = 2^2 + 4 * 2 + 2 = 14
p[2](3) = 3^2 + 4 * 3 + 2 = 23
p[2](4) = 4^2 + 4 * 4 + 2 = 34
p[2](5) = 5^2 + 4 * 5 + 2 = 47
p[2](6) = 6^2 + 4 * 6 + 2 = 62
Table 5_14_18.
i\j| 0 1 2 3 4 5 6 7 8 9
---+-----------------------------------------------------------------
0| 2 2 2 2 2 2 2 2 2 2
1| 2 3 7 18 47 123 322 843 2207 5778
2| 2 4 14 52 194 724 2702 10084 37634 140452
3| 2 5 23 110 527 2525 12098 57965 277727 1330670
4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
5| 2 7 47 322 2207 15127 103682 710647 4870847 33385282
6| 2 8 62 488 3842 30248 238142 1874888 14760962 116212808
7| 2 9 79 702 6239 55449 492802 4379769 38925119 345946302
8| 2 10 98 970 9602 95050 940898 9313930 92198402 912670090
9| 2 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
========================================================== p. 19
What is p[3](n) ?
We want to find integers a, b, c, d such that
p[3](n) = a * n^3 + b * n^2 + c * n + d = a(n,3).
p[3](0) = d = 2
p[3](1) = a + b + c + d = 18
p[3](2) = a * 8 + b * 4 + c * 2 + d = 52
p[3](3) = a * 27 + b * 9 + c * 3 + d = 110
This means solving this set of simultaneous equations:
d = 2
a + b + c + d = 18
8*a + 4*b + 2*c + d = 52
27*a + 9*b + 3*c + d = 110
Many mistakes later I got a=1, b=6, c=9, d=2 and so
p[3](n) = n^3 + 6 * n^2 + 9 * n + 2
To summarize, the first four polynomials to generate the
first four columns of Table 5_14_18 are
p[0](n) = 2
p[1](n) = 1 * n + 2
p[2](n) = 1 * n^2 + 4 * n + 2
p[3](n) = n^3 + 6 * n^2 + 9 * n + 2
Looking just at the coefficients, we get this table:
2
1 2
1 4 2
1 6 9 2
========================================================== p. 20
Hoping for a miracle in order to avoid solving larger sets
of simultaneous equations, I went to OEIS, entered "1, 6, 9, 2",
and was led to the (1,2)-Pascal triangle. (This did
not work when I tried it again more recently. Try it yourself
and see all the unbelievable places "1, 6, 9, 2" occurs.)
The (1,2) Pascal Triangle in table form:
i\j| 0 1 2 3 4 5 6 7 8 9
---+--------------------------------
0| 2 0 0 0 0 0 0 0 0 0
1| 1 2 0 0 0 0 0 0 0 0
2| 1 3 2 0 0 0 0 0 0 0
3| 1 4 5 _2_ 0 0 0 0 0 0
4| 1 5 _9_ 7 2 0 0 0 0 0
5| 1 _6_14 16 9 2 0 0 0 0
6|_1_ 7 20 30 25 11 2 0 0 0
7| 1 8 27 50 55 36 13 2 0 0
8| 1 9 35 77 105 91 49 15 2 0
9| 1 10 44 112 182 196 140 64 17 2
If you look at just the upward diagonals, you see:
i\j| 0 1 2 3 4 5
---+--------------
0| 2 0 0 0 0 0
1| 1 0 0 0 0 0
2| 1 2 0 0 0 0
3| 1 3 0 0 0 0
4| 1 4 2 0 0 0
5| 1 5 5 0 0 0
6|_1_6__9__2_0 0
7| 1 7 14 7 0 0
8| 1 8 20 16 2 0
9| 1 9 27 30 9 0
If you look only at the even numbered upward diagonals, you
see:
i\j| 0 1 2 3 4 5
---+----------------
0| 2 0 0 0 0 0
2| 1 2 0 0 0 0
4| 1 4 2 0 0 0
6| 1 6 9 2 0 0
8| 1 8 20 16 2 0
10| 1 10 35 50 25 2
But the first four lines contain exactly the coefficients
we computed to create the first four columns of Table 5_14_18.
2
1 2
1 4 2
1 6 9 2
1 8 20 16 2
1 10 35 50 25 2
The polynomials are:
p[0](n) = 2
p[1](n) = n + 2
p[2](n) = n^2 + 4 * n + 2
p[3](n) = n^3 + 6 * n^2 + 9 * n + 2
p[4](n) = n^4 + 8 * n^3 + 20 * n^2 + 16 * n + 2
p[5](n) = n^5 + 10 * n^4 + 35 * n^3 + 50 * n^2 + 25 * n + 2
I wrote a program to calculate the columns of a table, using
the even diagonals of the (1,2) Pascal triangle to define the
coefficients of the polynomials.
Call this algorithm A_ ("A blank").
Algorithm A_ generates the same table as algorithms A1 and A2.
By construction.
========================================================== p. 21
Evaluating p[0](n), p[0](n), p[0](n), p[0](n), p[0](n), p[0](n)
for n = 0, 1, 2, 3, 4, 5 to show how they calculate the columns
of Table 5_14_18.
p[0](n) = 2
p[0](0) = 2 = 2
p[0](1) = 2 = 2
p[0](2) = 2 = 2
p[0](3) = 2 = 2
p[0](4) = 2 = 2
p[0](5) = 2 = 2
p[1](n) = n + 2
p[1](0) = 0 + 2 = 2
p[1](1) = 1 + 2 = 3
p[1](2) = 2 + 2 = 4
p[1](3) = 3 + 2 = 5
p[1](4) = 4 + 2 = 6
p[1](5) = 5 + 2 = 7
p[2](n) = n^2 + 4 * n + 2
p[2](0) = 0^2 + 4 * 0 + 2 = 2
p[2](1) = 1^2 + 4 * 1 + 2 = 7
p[2](2) = 2^2 + 4 * 2 + 2 = 14
p[2](3) = 3^2 + 4 * 3 + 2 = 23
p[2](4) = 4^2 + 4 * 4 + 2 = 34
p[2](5) = 5^2 + 4 * 5 + 2 = 47
p[3](n) = n^3 + 6 * n^2 + 9 * n + 2
p[3](0) = 0^3 + 6 * 0^2 + 9 * 0 + 2 = 2
p[3](1) = 1^3 + 6 * 1^2 + 9 * 1 + 2 = 18
p[3](2) = 2^3 + 6 * 2^2 + 9 * 2 + 2 = 52
p[3](3) = 3^3 + 6 * 3^2 + 9 * 3 + 2 = 110
p[3](4) = 4^3 + 6 * 4^2 + 9 * 4 + 2 = 198
p[3](5) = 5^3 + 6 * 5^2 + 9 * 5 + 2 = 322
p[4](n) = n^4 + 8 * n^3 + 20 * n^2 + 16 * n + 2
p[4](0) = 0^4 + 8 * 0^3 + 20 * 0^2 + 16 * 0 + 2 = 2
p[4](1) = 1^4 + 8 * 1^3 + 20 * 1^2 + 16 * 1 + 2 = 47
p[4](2) = 2^4 + 8 * 2^3 + 20 * 2^2 + 16 * 2 + 2 = 194
p[4](3) = 3^4 + 8 * 3^3 + 20 * 3^2 + 16 * 3 + 2 = 527
p[4](4) = 4^4 + 8 * 4^3 + 20 * 4^2 + 16 * 4 + 2 = 1154
p[4](5) = 5^4 + 8 * 5^3 + 20 * 5^2 + 16 * 5 + 2 = 2207
p[5](n) = n^5 + 10 * n^4 + 35 * n^3 + 50 * n^2 + 25 * n + 2
p[5](0) = 0^5 + 10 * 0^4 + 35 * 0^3 + 50 * 0^2 + 25 * 0 + 2 = 2
p[5](1) = 1^5 + 10 * 1^4 + 35 * 1^3 + 50 * 1^2 + 25 * 1 + 2 = 123
p[5](2) = 2^5 + 10 * 2^4 + 35 * 2^3 + 50 * 2^2 + 25 * 2 + 2 = 724
p[5](3) = 3^5 + 10 * 3^4 + 35 * 3^3 + 50 * 3^2 + 25 * 3 + 2 = 2525
p[5](4) = 4^5 + 10 * 4^4 + 35 * 4^3 + 50 * 4^2 + 25 * 4 + 2 = 6726
p[5](5) = 5^5 + 10 * 5^4 + 35 * 5^3 + 50 * 5^2 + 25 * 5 + 2 = 15127
========================================================== p. 22
Encapsulate all of the above information in this table:
5 4 3 2 1 0 |i| 0 1 2 3 4 5
-----------------+-+-----------------------
0 0 0 0 0 2 |0| 2 2 2 2 2 2
0 0 0 0 1 2 |1| 2 3 7 18 47 123
0 0 0 1 4 2 |2| 2 4 14 52 194 724
0 0 1 6 9 2 |3| 2 5 23 110 527 2525
0 1 8 20 16 2 |4| 2 6 34 198 1154 6726
1 10 35 50 25 2 |5| 2 7 47 322 2207 15127
Take line i from the LHS
Construct a polynomial p[i](n)
using the values in line i
Evaluate p[i](n) for n = 0,1,2,...
to construct column i on the RHS.
========================================================== p. 23
It is not surprising that algorithm A_ exists. The
introduction showed that given any sequence of integers
n0, n1, n2, ...,
a polynomial p(n) can be created such that
p(0) = n0
p(1) = n1
p(2) = n2, etc.
========================================================== p. 24
Here is what is surprising.
The polynomials, p[0](n), p[1](n), p[2](n), ....,
can be defined recursively.
p[0](n) = 2
p[1](n) = n + 2
p[2](n) = n^2 + 4 * n + 2
p[3](n) = n^3 + 6 * n^2 + 9 * n + 2
p[4](n) = n^4 + 8 * n^3 + 20 * n^2 + 18 * n + 2
p[5](n) = n^5 + 10 * n^4 + 35 * n^3 + 50 * n^2 + 25 * n + 2
p[0](n) = 2
p[1](n) = n + 2
p[2](n) = (n+2) * p[1](n) - p[0](n)
= n^2 + 4*n + 4 - 2
= n^2 + 4*n + 2
p[3](n) = (n+2) * p[2](n) - p[1](n)
= n*(n^2 + 4*n + 2) + 2*(n^2 + 4*n + 2) - n - 2
= n^3 + 6*n^2 + 9*n + 2
p[4](n) = (n+2) * p[3](n) - p[2](n)
= n*(n^3 + 6*n^2 + 9*n + 2) + 2*(n^3 + 6*n^2 + 9*n + 2) - (n^2 + 4*n + 2)
= n^4 + 6*n^3 + 9*n^2 + n*2 + 2*n^3 + 12*n^2 + 18*n + 4 - n^2 - 4*n -2
= n^4 + 8*n^3 + 20*n^2 + 16*n + 2
p[5](n) = (n+2) * p[4](n) - p[3](n)
= n*(n^4 + 8 * n^3 + 20 * n^2 + 16 * n + 2) + 2*(n^4 + 8 * n^3 + 20 * n^2 + 16 * n + 2) - (n^3 + 6 * n^2 + 9 * n + 2)
= n^5 + 8*n^4 + 20*n^3 + 16*n^2 + 2*n + 2*n^4 + 16*n^3 + 40*n^2 + 32*n + 4 - n^3 - 6*n^2 - 9*n - 2
= n^5 + 10 * n^4 + 35 * n^3 + 50 * n^2 + 25 * n + 2
In general,
p[0](n) = 2; p[1](n) = n + 2; p[j](n) = (n+2) * p[j-1](n) - p[j-2](n)
Call this algorithm A0.
========================================================== p. 25
Here is another way of seeing the same result.
The coefficients for the first 6 polynomials are:
0. 2 = p[0](n)
1. 1 2 = p[1](n)
2 1 4 2 = p[2](n)
3. 1 6 9 2 = p[3](n)
4. 1 8 20 16 2 = p[4](n)
5. 1 10 35 50 25 2 = p[5](n)
The procedure for deriving them recursively is:
1 2 = p[1](n) = n + 2
x 1 2 times n + 2
---------------
2 4
1 2
---------------
1 4 4
- 2 minus p[0](n)
--------------
1 4 2 = p[2](n) = (n+2)*p[1](n)-p[0](n)
x 1 2 times n + 2
---------------
2 8 4
1 4 2
---------------------
1 6 10 4
- 1 2 minus p[1](n)
--------------------
1 6 9 2 = p[3](n) = (n+2)*p[2](n)-p[1](n)
x 1 2 times n + 2
---------------------
2 12 18 4
1 6 9 2
---------------------------
1 8 21 20 4
- 1 4 2 minus p[2](n)
---------------------------
1 8 20 16 2 = p[4](n) = (n+2)*p[3](n)-p[2](n)
x 1 2 times n + 2
---------------------------
2 16 40 32 4
1 8 20 16 2
---------------------------------
1 10 36 56 34 4
- 1 6 9 2 minus p[3](n)
---------------------------------
1 10 35 50 25 2 = p[5](n) = (n+2)*p[4](n-p[3](n)
========================================================== p. 26
Conclusion of Section A
Table 5_14_18. The even diagonals from the (1,2) Pascal Triangle. Source 1,2,0,2.
9 8 7 6 5 4 3 2 1 0 |i| 0 1 2 3 4 5 6 7 8 9
--------------------------------------+-+------------------------------------------------------------------
0 0 0 0 0 0 0 0 0 2 |0| 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 1 2 |1| 2 3 7 18 47 123 322 843 2207 5778
0 0 0 0 0 0 0 1 4 2 |2| 2 4 14 52 194 724 2702 10084 37634 140452
0 0 0 0 0 0 1 6 9 2 |3| 2 5 23 110 527 2525 12098 57965 277727 1330670
0 0 0 0 0 1 8 20 16 2 |4| 2 6 34 198 1154 6726 39202 228486 1331714 7761798
0 0 0 0 1 10 35 50 25 2 |5| 2 7 47 322 2207 15127 103682 710647 4870847 33385282
0 0 0 1 12 54 112 105 36 2 |6| 2 8 62 488 3842 30248 238142 1874888 14760962 116212808
0 0 1 14 77 210 294 196 49 2 |7| 2 9 79 702 6239 55449 492802 4379769 38925119 345946302
0 1 16 104 352 660 672 336 64 2 |8| 2 10 98 970 9602 95050 940898 9313930 92198402 912670090
1 18 135 546 1287 1782 1386 540 81 2 |9| 2 11 119 1298 14159 154451 1684802 18378371 200477279 2186871698
A0: p[0](n) = 2, for n >= 0.
p[1](n) = n + 2, for n >= 0.
p[j](n) = (n + 2) * p[j-1](n) - p[j-2](n), for j > 1, n >= 0.
A1: a(i,0) = 2, for i >= 0.
a(i,1) = i + 2, for i >= 0.
a(i,j) = (i + 2) * a(i,j-1) - a(i,j-2) for j > 1, i >= 0.
Note the symmetry between A0 and A1.
Note the syntax for A0 and A1 are (almost) identical.
Note that the semantics for A0 and A1 are very different! A1
defines calculations among integers. A0 describes a recursive
procedure for generating polynomials.
a(2,3) = 52 = (2 + 2) * 14 - 4 = 56 - 4 = 52
p[3](n) = (n + 2) * (n^2 + 4*n + 2) - (n + 2)
= n^3 + 4*n^2 + 2*n + 2*n^2 + 8*n + 4 - n - 2
= n^3 + 6*n^2 + 9*n + 2
so p[3](2) = 8 + 6*4 + 9*2 + 2
= 52
Question. Is Table 5_14_18 one of a kind? Or are there
other examples?
Answer: There are lots more. See Section D.
==========================================================
From nothing, beauty.
==========================================================
========================================================== p. 27
Section B. Online Encyclopedia of Integer Sequences (OEIS)
History
Founded by Neil Sloane
He began collecting sequences in 1964
Published sequences in two books, in 1973 and 1995
Created OEIS in 1996 with 10,000 sequences
OEIS now contains 315,000 sequences
CV for Sloane is at Sloane_CV
48,611 citations on Google Scholar as of June 29, 2016
Using OEIS.
To look up a sequence or an A-number
oeis.org
and enter the sequence or A-number in the box
Go to www.oeis.org/Submit.html
1. To create an account
You have to create an account before you can submit something to OEIS.
2. To login
3. To submit new work or a comment on the work of others
How to log in
Go to https://oeis.org/
Click 'login' in the upper right corner
How to edit
First log in. Then go to the array entry.
There will be the title line; then entries in the array;
then a line beginning "list; graph; . . .". Click on "edit;"
in this sequence.
For more info on submitting
https://oeis.org/wiki/Main_Page
Contributor's License
https://oeis.org/wiki/The_OEIS_Contributor%27s_License_Agreement
You yield total editorial control to OEIS
when you create an account.
If you submit something, you will probably not do it perfectly.
The editors may tidy up trivial format problems.
They will NOT fix mathematical problems.
Communication between contributor and editor(s) is rigid.
You submit. They email a response, such as "this is not clear".
You have to read their minds in order to figure out what
they think is a problem and then fix it.
You edit your contribution in order to fix mistakes.
You wait for a response from the editors. Nothing happens.
Finally you figure out that you have to click
"The changes are ready for review by an OEIS Editor."
at the end of your submission. This tells the editors
you (think you) have finished correcting your errors.
There are no email addresses for editors or contributors.
All communication with OEIS is done in this constrained format.
OEIS has two reasons for this
OEIS is not going to do contributors' work for them
OEIS thereby maintains a complete record of communication
between contributors and editors
========================================================== p. 28
Fun Stuff
OEIS can be fascinating to browse. For example...
oeis.org/A001835 a(n) = 4*a(n-1) - a(n-2), with a(0)=1, a(1)=1.
1, 1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841,...
sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571)...
- Gary W. Adamson, Dec 18 2007
But OEIS only states results. It does not explain. Frustrating.
Someplace OEIS says there is an example of two distinct sequences
which agree for the first 14,000+ entries, but then disagree.
If you find that reference, please let me know.
What is the smallest positive integer NOT on OEIS?
I accidentally stumbled onto 1044486.
Here is an idea for a sequence: all of the integers
which do not otherwise occur on OEIS.
XKCD already beat me to this; see xkcd.com/2016/
The index to OEIS is at http://oeis.org/wiki/Index_to_OEIS. Great fun to
browse through. Try going here and clicking on "humble numbers".
http://oeis.org/wiki/Index_to_OEIS:_Section_Ho
==========================================================
========================================================== p. 29
Section C. More algorithms.
We use OEIS to discover more patterns.
We showed above that Table 5_14_18 could be generated by
algorithms A0, A1, and A2.
Here we go through all the entries on OEIS for lines in Table
5_14_18 with the goal of finding more algorithms which generate
the table.
More algorithms
==========================================================
========================================================== p. 30
Section D. How to produce wisterian tables.
Method 1.
1. Create an (a,b) Pascal triangle.
a b
a a+b b
a 2a+b a+2b b
a 3a+b 3a+3b a+3b b
a 4a+b 6a+4b 4a+6b a+4b b
2. Extract the upward diagonals.
2. Select subsequences of the diagonals.
all, even, or odd.
3. Create polynomials p[i](n), using the values
in the diagonals as coefficients.
4. Create column i of a table by evaluating
polynomial p[i](n) for n = 0,1,2,3,....
Many examples are shown at More tables
Method 2. Seek a way to generate wisteria tables
independently of Pascal triangles.
Look at the A0 rules for generating tables by Method 1.
Discover they all fit in a tight mold.
Deliberately create an A0 rule which does not fit the mold.
Create the table. Find that it is wisterian.
Wonder: is it really outside the realm of tables stemming
from Pascal triangles?
==========================================================
========================================================== p. 31
Section E. Conclusion.
Definition. A table T of integers is wisterian if there exists
a sequence A0 of recursively defined polynomials p[i](n) such
that polynomial p[i](n) generates column i of table T when
evaluated for n = 0,1,2,....
Conjecture. For every wisteria table T with generating
polynomials A0 there is a sequence of recursion relations A1 such
that the i-th recursion relation defines the integers in row i of
T. Further, A0 and A1 are syntactically identical (though
semantically distinct since one defines polynomials and the other
defines recurrence relations).
What have we accomplished?
1. Claim. Wisteria tables are objects of mathematical
interest in and of themselves.
2. Claim. Arranging OEIS entries in tables, wisteria or
otherwise, will benefit OEIS in three ways.
a. It will reveal gaps where a rule is defined for some
entries, but not others, and should be defined for all. This
will encourage the gaps to be filled.
b. It will create deeper understanding of connections
between entries within a table.
c. It could raise questions about finding connections
between different tables.
========================================================== p. 32
Research
1. Prove the above conjecture.
2. Find wisteria tables which are demonstrably not derived
from Pascal triangles.
3. Given a table which obeys algorithms A0, A1, A2, A3, A4,
A5, and A6 (based on an infinitesimally small sample of the upper
lefthand corner of the table), prove mathematically that the
entire table is created by each of the algorithms.
4. Scavenge further. For each table in Section D
identify what flavor of A2, A3, A4, A5, and A6 it may obey.
5. Create a program which, given a table, shows what rules
the rows and columns obey. (This is impossibly general.)
6. Generate (a,b)-Pascal triangles where a and b can be negative.
See what happens.
7. Generate Pascal triangles where the third row consists of
arbitrary integers (a,b,c). See what happens.
========================================================== p. 33
Further Reading
Experimental Mathematics. en.wikipedia.org/wiki/Experimental_mathematics
Interview with Neil Sloane. https://www.quantamagazine.org/neil-sloane-connoisseur-of-number-sequences-20150806/?utm_content=buffere5b2b&utm_medium=social&utm_source=facebook.com&utm_campaign=buffer
"The On-Line Encyclopedia of Integer Sequences" by Neil Sloane in Notices of the AMS, Volume 65, Number 9.
https://www.ams.org/journals/notices/201809/rnoti-p1062.pdf
Linear Recurrence Equation. http://mathworld.wolfram.com/LinearRecurrenceEquation.html
Generating Function. http://mathworld.wolfram.com/GeneratingFunction.html
Stephen Wolfram Blog. http://blog.stephenwolfram.com/2017/03/two-hours-of-experimental-mathematics/
Some of the opinions of Doron Zeilberger which relate to the interests of the chapter.
Opinion149. Tic-Tac-Toe, Checkers, Chess, Go, and next is MATHEMATICS! (Written: March 22, 2016)
Opinion124. A Database is Worth a Thousand Mathematical Articles: An Ode
to Neil Sloane's On-line Encyclopedia of Integer Sequences (OEIS) (Written: May 22, 2012)
Opinion37. Guess What? Programming is Even More Fun Than Proving, and, More Importantly
It Gives As Much, If Not More, Insight and Understanding" (Written: April 15, 1999)
Acknowledgment. Many, many thanks to Bill Rubin for acting as
sounding board for ideas, for pushing the use of spell check and
html check, and for doing a great job as webmaster for the ACM
chapter site in general and for these foils in particular.