Automated Generation of Generating Functions Related to Generalized Stern's Diatomic Arrays in the footsteps of Richard Stanley

By Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

Written: March 23, 2021

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org

Using Symbolic Dynamic Programming we describe algorithms, fully implemented in Maple, for automatically generating generating functions introduced by Richard Stanley in his study of generalized Stern arrays, generalized even further, to arrays defined in terms of general sequences satisfying linear recurrences with constant coefficients, rather than just the Fibonacci and k-bonacci sequences.

## Maple packages

• StanleyStern.txt, a Maple package to automatically generate generating functions for generalized Stern sums conisered by Richard Stanley Stern's diaatomic array and generalized versions of it.

• SternCF.txt, A Maple package that studies C-finite generalizations of Stern's diatomic array inspired by the Fibonacci and k-bonacci generalizations considered by Richard Stanley.

## Sample Input and Output Files for StanleyStern.txt

• If you want to see a computer-generated book with generating functions for the sums of the rth power of the rows in the ORIGINAL Stern diatomic array, for r from 1 to 15 considered by Richard Stanley, using the NON-EXPERIMENTAL approach, that solves a linear system equation with SYMBOLIC coefficients
The input gives you the output   .

• If you want to see a computer-generated book with generating functions for the sums of the rth power of the rows in the ORIGINAL Stern diatomic array, for r from 1 to 15 considered by Richard Stanley, using the EXPERIMENTAL (yet rigorous!) approach, that solves a linear system of equation with NUMERIC coefficients
The input gives you the output   .

• Since the latter approach is much faster, we can easily get the generating functions for r from 1 to 25
The input gives you the output   .

• If you want to see a computer-generated book with generating functions for the sums of products of r consecutive terms of the rows in the ORIGINAL Stern diatomic array, for r from 1 to 9 considered by Richard Stanley, using the NON-EXPERIMENTAL approach
The input gives you the output   .

• If you want to see a computer-generated book with generating functions for the sums of products of r consecutive terms of the rows in the ORIGINAL Stern diatomic array, for r from 1 to 9 considered by Richard Stanley, using the (faster, in this case, but not that fast), EXPERIMENTAL approach
The input gives you the output.   .

## Sample Input and Output Files for StanleyCF.txt

• If you want to see generating functions for the sum of the r-th power of the coefficients of the polynomial

Prod(1 + xFi + 1 + xFi+2 , i=1..n),

where Fi are the Fibonacci numbers,

for r from 1 to 6 [The case r=2 is given on line 3 of p. 10 of Richard Stanley's "Theorems and Conjectures on Some rational generating functions"]
The input gives you the output   .

[Of course, we used the NON-EXPERIMENTAL approach, since the experimental approach is hopeless]

For a version that only tells you the dimensions of the matrices, and uses it to get the first 30 terms
The input gives you the output   .

• Letting

Sum( a(n,k) xk ,k=0..infinity)=Prod(1 + xFi + 1 + xFi+2 , i=1..n)

If you want to see generating functions for the sequences

Sum(a(n,k)*a(n,k+1) , k=0..infinity)   ,
Sum(a(n,k)*a(n,k+1)*a(n,k+2) , k=0..infinity)    ,
Sum(a(n,k)*a(n,k+1)*a(n,k+2)*a(n,k+3) , k=0..infinity)    ,

The input gives you the output   .

• Let Ti be the Tribonacci numbers (defined by T1=1 ,T2=1, ,T3=1, and for i ≥ 4

Ti = Ti-1 +Ti-2 + Ti-3  ,

Let

Sum( a(n,k) xk ,k=0..infinity)=Prod(1 + xTi + 1 + xTi+2 + xTi+3 , i=1..n)

If you want to see generating functions for the sequences

Sum(a(n,k)r,k=0..infinity)   for r=1,2,3

The input gives you the output.   .

• Since things are getting complicated, for r=4, we had to resort to just getting the huge matrix, and enables fast computation of the sequences. So if you want to see a matrix version of the above, including r=4 Let Ti be the Tribonacci numbers, and let
The input gives you the output   .

Note that the matrix for the r=4 case has dimension 7245

• As above, let Ti be the Tribonacci numbers, and let

Sum( a(n,k) xk ,k=0..infinity)=Prod(1 + xTi + 1 + xTi+2 + xTi+3 , i=1..n)

If you want to see generating functions for the sequences

Sum(a(n,k)a(n,k+1),k=0..infinity)

Note that for

Sum(a(n,k)a(n,k+1)a(n,k+2),k=0..infinity)

it exceeded the number of equations that we allowed, but see below.

The input gives you the output   .

• If you want to see the first few terms (by computing the matrix, but not solving the system) for

Sum(a(n,k)a(n,k+1)a(n,k+2),k=0..infinity)

The input gives you the output   .

• Let Qi be the Quadronacci numbers (defined by Q1=1 ,Q2=1 , Q3=1, , Q4=1, and for i ≥ 5

Qi = Qi-1 + Qi-2 + Qi-3 + Qi-4  ,  ,

Let

Sum( a(n,k) xk ,k=0..infinity) = Prod(1 + xQi + 1 + xQi+2 + xQi+3 + xQi+4 , i=1..n)

If you want to see generating functions for the sequences

Sum(a(n,k)2 , k=0..infinity)

The input gives you the output   .

• Again, let Qi be the Quadronacci numbers (defined by Q1=1 ,Q2=1 , Q3=1, , Q4=1, and for i ≥ 5

Qi = Qi-1 + Qi-2 + Qi-3 + Qi-4  ,  ,

and let

Sum( a(n,k) xk ,k=0..infinity) = Prod(1 + xQi + 1 + xQi+2 + xQi+3 + xQi+4 , i=1..n)

If you want to see generating functions for the sequences

Sum(a(n,k)a(n,k+1) , k=0..infinity)

The input gives you the output   .

• If you want to see a more succinct version of the previous file, just stating the dimension of the matrix and giving the first 30 terms

The input gives you the output   .

• Let Pi be the Pentaronacci numbers (defined by P1=1 ,P2=1 , P3=1, , P4=1, , P5=1, and for i ≥ 6

Pi = Pi-1 + Pi-2 + Pi-3 + Pi-4 + Pi-5  ,  ,

Let

Sum( a(n,k) xk ,k=0..infinity) = Prod(1 + xPi + 1 + xPi+2 + xPi+3 + xPi+4 + xPi+5 , i=1..n)

Then it is too complicated to get the generating function, since the matrix has dimension 12751, but we found the matrix, that enabled to compute the first few terms of

Sum(a(n,k)2 , k=0..infinity)

The input gives you the output   .

• If you want to see a table of the generating functions Jr(k)(t,x) defined in Richard Stanley's article (arXiv:2101.02131v2) for r from 2 to 10 and k from 2 to 4,

The input gives you the output   .

• If you want to see a table of the generating functions Jr(k)(1,x) defined in Richard Stanley's article (arXiv:2101.02131v2) for r from 2 to 20 and GENERAL (SYMBOLIC!) k [conjectured and verified for k=2,3,4]

The input gives you the output   .

• If you want to see a the first 26 terms in the (most probably) very hard-to-compute sequnce for the sum of squares of the coefficeints of Product(1+x^(2^i+(-1)^i)+x^(2^(i+1)+(-1)^(i+1)),i=0..n-1)

The input gives you the output   .

• [Added March 30, 2021] If you want to see generating functions for the sum of the r-th power of the coefficients of Prod(1+x^f(i+2),i=1..n) where f(i) is a solution of the recurrence f(i)=f(i-1)+f(i-3) that (with initial conditions f(1)=f(2)=f(3)=1) Richard Stanley on the top of p. 21 of his
article (arXiv:2101.02131v2)
doubted is "nice", for r=1,2,3,4

The input gives you the output   .

• [Added March 30, 2021] If you want to see generating functions for the sum of a(n,k)(a,k+1)...a(n,k+r-1) over k, where a(n,k) are the coefficients of Prod(1+x^f(i+2),i=1..n) where f(i) is a solution of the recurrence f(i)=f(i-1)+f(i-3), f(1)=f(2)=f(3)=1 for r=1,2,3

The input gives you the output   .

• [Added March 31, 2021] If you want to see generating functions for the sum of the r-th power of the coefficients of Prod(1+x^f(i+2),i=1..n) where f(i) is a solution of the recurrence f(i)=f(i-2)+f(i-3) that Richard Stanley on the top of p. 21 of his
article (arXiv:2101.02131v2)
doubted is "nice", for r=1,2,3

The input gives you the output   .

• [Added March 31, 2021] If you want to see generating functions for the sum of a(n,k)(a,k+1)...a(n,k+r-1) over k, where a(n,k) are the coefficients of Prod(1+x^f(i+2),i=1..n) where f(i) is a solution of the recurrence f(i)=f(i-2)+f(i-3) for r=1,2

The input gives you the output   .

Personal Journal of SBE and DZ