OFFSET
1,6
COMMENTS
The Jump Sum Recursion Triangle is defined as a row by row reading of the coefficients of the recursions satisfied by the error term between Pascal-Triangle j-jump sums and 2^(jm)/j. To clarify this, define the j-jump sum, S(j,n)=Sum_{m= -oo..oo} C(n,jm), with C(x,y) the binomial coefficient if 0<=y<=x and 0 otherwise. It is known that S(1,n)=2^n and S(2,n)=2^(n-1). This suggests the heuristic that S(j,n) is approximately 2^n/j and motivates looking at the integral error terms, jS(j,n)-2^n. So, for fixed j, define the sequence, G(j,m)=G(m)=jS(j,mj)-2^(mj), and let p(j,X) be the characteristic polynomials of the sequence. The Jump Sum Recursion Triangle is defined as a row by row reading of the coefficients of p(1,X), p(2,X), p(3, X), p(4, X)... .
REFERENCES
Charles Cook and Rebecca Hillman, Some Jump Sum Patterns For the Rows of Pascal's and Related Triangles, Congressus Numerantium, 2010, pp. 255-267.
Russell Jay Hendel, Jump Sum Recursions, 16th Fibonacci Conference, Rochester NY, 2014.
LINKS
Michel Marcus, Table of n, a(n) for n = 1..650
John B. Dobson, A matrix variation on Ramus's identity for lacunary sums of binomial coefficients, arXiv preprint arXiv:1610.09361 [math.NT], 2016.
FORMULA
The following theorem can be proved: For j>=3, let w be a primitive j-th root of unity. Let L(k)=Sum_{p=0..j-1} c(p)w^(kp) with c(0)=2 and c(i)=C(j,i) if i>0. Then p(j,X)=(X-L(1))(X-L(2))...(X-L([(n-1)/2])). For example: If j=3, then w is a primitive cube root of unity and [(3-1)/2]=1. We have L(1)=2+3w+3w^2=-1 and X-L(1)=X+1 which is p(3,X) and corresponds to the 3rd row (terms 3 and 4) in the Jump Sum Recursion Triangle.
EXAMPLE
Suppose j=3. Then using our definition, S(3,3)=C(3,0)+C(3,3)=2, S(3,6)=C(6,0)+C(6,3)+C(6,6) = 1+20+1=22 (To explain the name "jump sum," we note, that we don't sum the Pascal Row across, but jump in steps of 3 when taking the sum). G(3,1)=G(1)=3S(3,3)-2^3=-2 and G(2)=3S(3,6)-2^6=2. Clearly, G(2)=-G(1). In fact, the sequence G(m)= G(3,m) - -2,2,-2,2,... - satisfies the recursion G(m)+G(m-1)=0 with characteristic equation X+1. Hence, the 3rd row in the Jump Sum Recursion Triangle is 1,1. Similarly, we can calculate that the sequence G(m)=G(m,4) which is, -8,32,-256,1024,..., which satisfies the recursions G(m)+4G(m-1)=0 with characteristic equation X+4. Hence, the 4th row of the Jump Sum Recursion Triangle is 1,4. Since S(n,1)=2^n and S(n,2)=2^(n-1), we have 1S(n,1)-2^n=0 and 2S(n,2)-2^(n-1)=0 showing that the sequences G(m,1) and G(m,2) satisfy the zero recursion, G(m)=0. Hence the first two rows of the Jump Sum triangle are identically 0.
The Jump Sum Triangle starts:
0;
0;
1, 1;
1, 4;
1, 11, -1;
1, 26, -27;
1, 57, -289, -1;
1, 120, -2160, -256;
1, 247, -13359, -13604, 1;
1, 502, -73749, -383750, 3125;
...
PROG
(PARI)
/* Function CreateTriangle produces first r rows of the Jump Sum Recursion Triangle*/
CreateTriangle(r) ={
/* First two rows created manually */
print(1, " ", [0]);
print(2, " ", [0]);
/* Create r rows of Pascal's triangle: m[i, j]= C(i, j)*/
m=matrix(r, r, i, j, 0);
m[1, 1]=1;
m[1, 2]=1;
for(i=2, r, m[i, 1]=1);
for(i=2, r, for(j=2, r, m[i, j]=m[i-1, j]+m[i-1, j-1]));
/*Loop to create rows 3, 4, 5, ..., r of Jump Sum Recursion Triangle */
for(o=3, r,
/* We create a modified Binomial Coefficient Circulant Matrix, n. The first row of n is 2, C(o, 2), C(o, 3), ..., C(o, o-1). To motivate this we extend our definitions above as follows:Define S(j, n, k)=Sum_{m=-oo..oo} C(n, k+jm), define G(m, k)=jS(j, mj, k)-2^(mj), and define G(m)= <G(m, 0), G(m, 1), ..., G(m, j-1)>. Then n*G(m) = G(m+1). This gives a matrix representation for the sequence G. The j-th row of the Jump Sum Recursion Triangle which are the coefficients of the recursion satisfied by G is equal to the minimal polynomial satisfied by n. Hence we can print out the triangle by printing out the coefficients of the minimal polynomials*/
n=matrix(o, o, i, j, 0);
for(i=1, o, n[i, i]=2);
for(j=1, o-1, for(i=1, o-j, n[i, i+j]=m[o, o+1-j]));
for(i=2, o, for(j=1, i-1, n[i, j]=m[o, o+1-i+j]));
/* Construct minimal polynomial by multiplying all factors
without multiplicity and avoiding factors X-2^n and X */
f=factor(charpoly(n));
g=length(f[, 1]);
h=1;
for(i=2, g, if(f[i, 1]==x, h, h=h*f[i, 1]));
print(o, " ", Vec(h));
)};
/*The first 11 rows of the Jump Sum Recursion Triangle, listed in the DATA step, can be obtained by calling CreateTriangle with argument r=11.*/
CreateTriangle(11);
CROSSREFS
KEYWORD
sign,eigen,easy,tabf
AUTHOR
Russell Jay Hendel, Jul 01 2014
STATUS
approved