cp's OEIS Frontend

Let the triangle = M, then M^n * [1, 1, 0, 0, 0, ...] generates rows of triangle A118800. M^n * [1, 0, 0, 0, ...] generates rows of triangle A038207.

Eigensequence of the triangle = the Pell numbers, A000129: (1, 2, 5, 12, 29, ...). - Gary W. Adamson, Dec 29 2008

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.