|
| |
|
|
A332636
|
|
Two-parameter family of recursively defined triangles, T(m,t), whose rows right-padded with zeros appear in the limiting sequence of families of certain linear recursive sequences. The data presents the sequence of triangles T(2,t) by ascending antidiagonals.
|
|
0
|
|
|
|
1, 1, -1, 1, -1, -1, 1, -1, -1, 2, 1, -1, -1, 2, 1, 1, -1, -1, 2, -1, -3, 1, -1, -1, 2, -1, 2, 1, 1, -1, -1, 2, -1, 0, -3, 1, 1, -1, -1, 2, -1, 0, 2, 1, -3, 1, -1, -1, 2, -1, 0, 0, -3, 1, -1, 1, -1, -1, 2, -1, 0, 0, 2, 1, -3, 9, 1, -1, -1, 2, -1, 0, 0, 0, -3, 1, 3, -4, 1, -1, -1, 2, -1, 0, 0, 0, 2, 1, -3, -5, -6, 1, -1, -1, 2, -1, 0, 0, 0, 0, -3, 1, 3, 10, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,10
|
|
|
COMMENTS
|
For fixed t >= 1, m >= 1 we can define a triangle as follows: Let T(1,1)=1, T(1,2)=-1, and T(1,x)=0, if x < 1 or x > 2. For p >= 1, define T(p+1,q) = -(m-1)*T(p,q) + (m-1)*T(p,q-1) + 2*T(p,q-1-t) - T(p,q-2-t).
It is easy to prove that T(p,1) = -(m-1)^(p-1) and T(p,2+(p-1)*(t+2)) = (-1)^p. Thus we may speak of the p-th row, T(p), of the triangle, whose length is 2+(p-1)*(t+2).
It is also easy to prove that the sum of T(p,q) for fixed p over all q is 0.
Using the same fixed t and m, we can define a family of recursive sequences whose k-th member, k >= t+3, is defined by the recursion G(n) = G(n-k) - Sum_{i=1..k-1} G(n-k+i) - (m-1)*G(n-k+t+1) with initial conditions G(1)=1, G(i)=0, i=2,3,...,k. Then for any fixed n, for all large k, the first k+(n-1)*(k-t-1) terms of G are 1, 0^{k-1}, T(1), 0^z(1), T(2), 0^z(2), ..., T(n), 0^z(n).
Proof: Recall that to every recursive sequence there is an underlying recursion and an associated characteristic polynomial. Furthermore, the sequences of two recursions (with the same initial conditions) are identical iff their characteristic polynomials are each divisible by the minimal polynomial of the sequence. Fix positive integers m and t. Let p(x) be the characteristic polynomial of the k-th order recursion: p(x) = -1 + x + x^2 + ... + x^k + (m-1)*x^(t+1). Let t(x) be the characteristic polynomial of the recursion for the sequence obtained from the triangle with rows of length k - t - 1 laid out row by row: t(x) = 1 - 2*x - (m-1)*x^(k-t-1) + (m-1)*x^(k-t) + x^(k+1). Then t(x)/p(x) = x - 1, proving that the two sequences are identical. The triangle appearance is driven by the large gap in exponents in t(x) (x^(k+1) versus x^(k-t)). This "naturally" allows writing the sequence in rows such that the previous row for the same column corresponds to the difference in positions (k+1) and (k-t).
For m=1, t=1 the triangle sequence, with zeros removed, becomes A118800.
The collection of k-th order recursions has a natural interpretation in terms of generalizations of the Fibonacci numbers. Define the Generalized Fibonacci numbers of order k by the recursion K(n) = Sum_{i=1..k} K(n-i), with initial conditions K(0)=0, K(i)=1, 1 <= i <= k-1. Further define G(n) = K(-n). (For k = 2, the [K(n)] are the Fibonacci numbers and for k = 3 they are the tribonacci numbers.) Then [G(n)] satisfies the recursion G(n) = G(n-k) - Sum_{i=1..k-1} G(n-k+i). (For purposes of reference later on we may suppose initial conditions G(i)=1, 1 <= i <= k-1, G(k)=0.) In other words, the recursions satisfied by the Generalized Fibonacci numbers over negative indices are identical to the recursions we presented in this OEIS sequence above with t = 1 and m = 1 and the resulting triangle [T(i, j)] satisfies almost the same recursion as in sequence A118800 (the reason for the difference lies in the initial conditions). More precisely, the first row of the triangle [T(1, 1), T(1, 2) = [0, -(k-3)]. Boundary conditions for the rightmost and leftmost diagonals are given as follows: For i >= 1, T(i, 1) = -(2^(i-1)-1) and T(i, i+1) = (-1)^i (k-2+(-1)^i). Then for i >= 2, 2 <= j <= i, T(i, j) = 2*T(i-1, j) - T(i-1, j-1), the recursion used for the triangle in A118800 and used in this OEIS sequence for the case t = 1 and m = 1. Paul Young (see link) gives a p-adic proof of the lack of zeros among negative indices for certain Generalized Fibonacci sequences. The study presented in this OEIS sequence arose while attempting to find an inductive proof of this result which however failed. However, Hendel made the following conjecture in the problem session at West Coast Number Theory (see link). Consistent with the observations made in this OEIS sequence, when the recursion (after the initial row of length k-1) is arranged in blocks of k, then the first k-1 rows are the triangle entries right-padded with ones. It is easy to prove that these rows (for k >= 4) have no zeros. Consistent with the results in this OEIS sequence, one can show that G(k^2-1) = K(-(k^2-k-1)) = T(k-1, k). Hendel conjectured that the absolute value of G(k^2-1) or T(-(k^2-k-1)) is a minimum over the rest of the sequence, that is, |G(k^2-1)| < G(n), n >= k^2. Although it is stated on the WCNT conference that some headway had been made, these attempts failed (so the conjecture is still open). The reason for reformulating this OEIS sequence using initial conditions of mostly zeros instead of ones is that the triangle boundaries also satisfy the triangle recursion and the right-padding of zeros is more natural than the right-padding of ones.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let T(1,1)=1, T(1,2)=-1, and T(1,x)=0, if x < 1 or x > 2. For p >= 1, define T(p+1,q) = -(m-1)*T(p,q) + (m-1)*T(p,q-1) + 2*T(p,q-1-t) - T(p,q-2-t).
Alternatively, for k >= t+3, define the k-th member of a family of recursions by G(n) = G(n-k) - Sum_{i=1..k-1} G(n-k+i) - (m-1)*G(n-k+t+1) and initial conditions G(1)=1, G(i)=0, i=2,3,...,k. Then for any fixed n, for all large k, the first k+(n-1)*(k-t-1) terms of G are 1, 0^(k-1), T(1), 0^z(1), T(2), 0^z(2), ..., T(n), 0^z(n) with the z(i) positive integers, with T(i) rows of a triangle with length 2+(i-1)*(t+2) and such that length(T(i)) + z(i) = k-t-1.
|
|
|
EXAMPLE
|
The first 4 triangle rows of T(2,1).
1 -1
-1 2 1 -3 1
1 -3 -1 9 -4 -6 5 -1
-1 4 0 -17 14 21 -28 -2 15 -7 1
The first 3 triangle rows of T(2,2).
1 -1
-1 2 -1 2 -3 1
1 -3 3 -5 10 -8 6 -8 5 -1
The first 3 triangle rows of T(2,3).
1 -1
-1 2 -1 0 2 -3 1
1 -3 3 -1 -4 10 -8 2 4 -8 5 -1
The first 3 triangle rows of T(3,3).
1 -1
-2 4 -2 0 2 -3 1
4 -12 12 -4 -8 20 -16 4 4 -8 5 1
The first 67 values (G(1)..G(67)) of the k=15th member of the family of recursive G sequences, with m=2, t=1, laid out as an initial row of 15 numbers followed by 4 rows of 13 members. As can be seen, the initial segments of lengths 2, 5, 8, 11 of rows 2 through 5 respectively are 1, -1 (2nd row), -1, 2, 1, -3, 1 (3rd row), 1, -3, -1, 9, -4, -6, 5, -1 (4th row), -1, 4, 0, -17, 14, 21, -28, -2, 15, -7, 1 (5th row) and these are identical to the first 4 triangle rows in the t=1, m=2 case confirming the empirical observation that both the triangle recursion and the family of G sequences give rise to the same triangles.
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 -1 0 0 0 0 0 0 0 0 0 0 0
-1 2 1 -3 1 0 0 0 0 0 0 0 0
1 -3 -1 9 -4 -6 5 -1 0 0 0 0 0
-1 4 0 -17 14 21 -28 -2 15 -7 1 0 0
For m=2, the first 16 members of the first 14 triangles (t=1, t=2, ..., t=14) with each triangle laid out row by row. The ascending diagonals in the data section can be produced from this array.
t\n | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
-----+----------------------------------------------
t=1 | 1 -1 -1 2 1 -3 1 1 -3 -1 9 -4 -6 5 -1 -1
t=2 | 1 -1 -1 2 -1 2 -3 1 1 -3 3 -5 10 -8 6 -8
t=3 | 1 -1 -1 2 -1 0 2 -3 1 1 -3 3 -1 -4 10 -8
t=4 | 1 -1 -1 2 -1 0 0 2 -3 1 1 -3 3 -1 0 -4
t=5 | 1 -1 -1 2 -1 0 0 0 2 -3 1 1 -3 3 -1 0
t=6 | 1 -1 -1 2 -1 0 0 0 0 2 -3 1 1 -3 3 -1
t=7 | 1 -1 -1 2 -1 0 0 0 0 0 2 -3 1 1 -3 3
t=8 | 1 -1 -1 2 -1 0 0 0 0 0 0 2 -3 1 1 -3
t=9 | 1 -1 -1 2 -1 0 0 0 0 0 0 0 2 -3 1 1
t=10 | 1 -1 -1 2 -1 0 0 0 0 0 0 0 0 2 -3 1
t=11 | 1 -1 -1 2 -1 0 0 0 0 0 0 0 0 0 2 -3
t=12 | 1 -1 -1 2 -1 0 0 0 0 0 0 0 0 0 0 2
t=13 | 1 -1 -1 2 -1 0 0 0 0 0 0 0 0 0 0 0
t=14 | 1 -1 -1 2 -1 0 0 0 0 0 0 0 0 0 0 0
For m=3, the first 16 members of the first 14 triangles (t=1, t=2, ..., t=14) with each triangle laid out row by row.
t\n | 1 2 3 4 5 6 7 8 9 10 11 12 13 14
-----+----------------------------------------------
t=1 | 1 -1 -2 4 0 -3 1 4 -12 4 16 -12 -4 5
t=2 | 1 -1 -2 4 -2 2 -3 1 4 -12 12 -12 20 -16
t=3 | 1 -1 -2 4 -2 0 2 -3 1 4 -12 12 -4 -8
t=4 | 1 -1 -2 4 -2 0 0 2 -3 1 4 -12 12 -4
t=5 | 1 -1 -2 4 -2 0 0 0 2 -3 1 4 -12 12
t=6 | 1 -1 -2 4 -2 0 0 0 0 2 -3 1 4 -12
t=7 | 1 -1 -2 4 -2 0 0 0 0 0 2 -3 1 4
t=8 | 1 -1 -2 4 -2 0 0 0 0 0 0 2 -3 1
t=9 | 1 -1 -2 4 -2 0 0 0 0 0 0 0 2 -3
t=10 | 1 -1 -2 4 -2 0 0 0 0 0 0 0 0 2
t=11 | 1 -1 -2 4 -2 0 0 0 0 0 0 0 0 0
t=12 | 1 -1 -2 4 -2 0 0 0 0 0 0 0 0 0
t=13 | 1 -1 -2 4 -2 0 0 0 0 0 0 0 0 0
t=14 | 1 -1 -2 4 -2 0 0 0 0 0 0 0 0 0
25 values, (K(0)..K(-24)) laid out in rows of 5, for the nonpositive indices of the Generalized Fibonacci numbers of order 5.
0 -2 1 1 1
-1 -4 4 1 1
-3 -7 12 -2 1
-7 -11 31 -16 4
|
|
|
PROG
|
(PARI)
TRIANGLE(m, t, r)={\\Prints r rows of T(m, t)
local(OFFSET, MAXLENGTH, i, j, T1, T2); OFFSET = t+2; MAXLENGTH=2+(r-1)*(t+2);
T=matrix(r, OFFSET+MAXLENGTH, i, j, 0); T[1, OFFSET+1]=1; T[1, OFFSET+2]=-1;
for(i=2, r, for(j=OFFSET+1, OFFSET+MAXLENGTH, T[i, j]=-(m-1)*T[i-1, j]+(m-1)*T[i-1, j-1]+2*T[i-1, j-1-t]-T[i-1, j-2-t]));
T2=matrix(r, MAXLENGTH, i, j, 0);
for(i=1, r, for(j=1, MAXLENGTH, T2[i, j]=T[i, OFFSET+j])); printp(T2); }
(PARI)
RECURSION(m, t, k, r)={
\\Prints (G(k+1)..G(k+r*(k-t-1))) of k-th recursion as r rows
\\G is k-th member of recursive family with parameters m, t
local(LENGTH, i, v, s, l); v=vector(k, i, 0); LENGTH=k-t-1;
G=vector(k+r*LENGTH, i, 0); G[1]=1; R=vector(k, i, -1); R[1]=1; R[t+2]=-m;
for(i=k+1, k+r*LENGTH, for(j=1, #v, v[j]=G[i-1-#v+j]); s=0; for(l=1, #v, s=s+R[l]*v[l]; G[i]=s));
G2=matrix(r, LENGTH, i, j, 0);
for(i=1, r, for(j=1, LENGTH, G2[i, j] = G[k+(i-1)*LENGTH+j])); printp(G2); }
(PARI)
RECURSION2(k)={
\\Prints (K(0)..K(-(k^2-k-1)) of Generalized Fibonacci numbers
\\Prints k-1 rows (excluding initial conditions) of length k
local(LENGTH, i, v, s, l); v=vector(k, i, 0); LENGTH=k; r=k-1; G=vector(k+r*LENGTH, i, 1); G[1]=k-1; R=vector(k, i, -1); R[1]=1;
for(i=k+1, k+r*LENGTH, for(j=1, #v, v[j]=G[i-1-#v+j]); s=0; for(l=1, #v, s=s+R[l]*v[l]; G[i]=s));
G2=matrix(r, LENGTH, i, j, 0);
for(i=1, r, for(j=1, LENGTH, G2[i, j] = G[k+(i-1)*LENGTH+j])); printp(G2); }
|
|
|
CROSSREFS
|
A118800 gives the nonzero entries of the sequence for t=1 and m=1.
|
|
|
KEYWORD
|
sign,tabf,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
