cp's OEIS Frontend

T(k, n) is even if k is odd.

T(k, n) = T(k, n+1) for n = k/2 - 2 if k >= 6 is even.

T(k, n) = T(k, n+2) for n = (k-1)/2 - 2 if k >= 7 is odd.

For fixed n, T(k, n) is linear in k.

The T(k, j) contribute coefficients to a closed formula for the sum of the first n+1 squares of the k-generalized Fibonacci numbers, F(k, j) = A092921(k, j). See A343138 for sums of squares of F(k, j). See the Formula section for closed formula. Although other sequences occur in coefficients in the closed formula for sums of squares, they are linear in nature. All coefficient sequences are mentioned in the arXiv link. The closed formula generalizes results of Schumacher (see References) for the cases k=3 and k=4 with a uniform proof method (see arXiv link).

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.

The main theorem of the Griffith-Bramham paper found in the LINKS section is the equivalence of the following alternate definitions for a(n). (I) a(n) equals the convolution of the Lucas numbers (A000032) and the Jacobsthal numbers (A001045), where, as usual, the m-th term of the convolution of sequences {b(n)}{n>=0} and {c(n)}{n>-0} equals Sum_{t+s=m} b(t)* c(s). (II) a(n) = A014551(n+1)-A000032(n+1), the difference of the Lucas-Jacobsthal numbers and the Lucas numbers with a shift of 1. The authors prove the equivalence of (I) and (II) using the generating function method.

Referring to the simplicity of definition (II), the authors formulate the following open question: "Since the convolution takes such a simple form, we ask whether it is possible to obtain a purely combinatorial proof of this result."

I would suggest another open question: Are there convolutions of other linear homogeneous recurrences with constant coefficients which are equivalent to very simple forms?

There are 3 equivalent ways to define this sequence:

#1) Recursively defined polynomial sequence:

G_0(x)=1, G_1(x)=1+x; G_n=(1-2x)G_{n-1}+(x-x^2)G_{n-2}. One can then form a triangle whose n-th row lists the coefficients of G_n(x) starting from the constant term. The list of these rows forms the sequence. It follows that an explicit formula for G_n is G_n(x)=(1+2x)(1-x)^n-2x(-x)^n.

#2) Recursively defined triangle:

Define an array g^(i)n as follows: i) Leftmost column: g^(0)_n=1, n >=0; ii) Define the diagonal sequence D_n = g^(n)_n by D_0=0, D_1=1 and D_n=-2D{n-1}- D_{n-2}; iii) Boundary conditions: g^(i)n=0 if i<0, n<0 or n>i; iv) g^(i)_n - g^(i){n-1}= -g^(i-1)_{n-1} for n>=2, 1 <=i <=n-1. It follows that g^(i)_n = -(-1)^j(2 C(n,j-1)-C(n,j)) with C(n,j) the binomial coefficient.

#3) Polynomial columns:

g^(0)n =1 (n >=0); g^(i)_n= (-1)^i 1/i! (n-(3i-1))(n){i-1} for i>=1 and n>=i (g^(i)n is 0 elsewhere). Here (n)_m is the falling factorial with (n)_0=1 and (n){m+1}=(n)_m (n-m).

The polynomials G_n = (1+2x)(1-x)^n-2x(-x)^n have interesting limit properties. (All limits are for fixed x as n goes to infinity.)

1) lim G_n(-1) = lim -(2^n-2) = minus infinity

2) lim G_n(x) = minus infinity, for -1 <= x < -1/2

3) lim G_n(-1/2) = lim (1/2)^n =0

4) lim G_n(x) = positive infinity, for -1/2 < x <0

5) lim G_n(0) = 1 (in fact G_n(0)=1 for all n)

6) lim G_n(x) = 0, for 0

7) lim G_n(1) = lim -(-1)^n 2, diverges by oscillation

There are other interesting limits. For example, although for all n, G_n(0)=1, nevertheless lim G_n(1/n) = 1/e.