Of fibonomials, pellonomials, and tribonomials, etc

Question

I. Linear recurrence with order 2

Given the Fibonacci numbers $F_n$, we have

$$\begin{aligned} &F_n+F_{n+1}-F_{n+2}=0\\[1mm] &F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2=0\\[1mm] &F_n^3+3F_{n+1}^3-6F_{n+2}^3-3F_{n+3}^3+F_{n+4}^3=0\\ &\small\text{and so on.} \end{aligned}$$

The coefficients are called fibonomials. (The version for the Pell numbers are quaintly called the pellonomials.)

II. Linear recurrence with order 3

For the tribonacci numbers $T_n$, we have,

$$\begin{aligned} &T_n+T_{n+1}+T_{n+2}-T_{n+\color{brown}3}=0\\[1mm] &T_n^2 - T_{n + 2}^2 + 6T_{n + 3}^2 - 3T_{n + 4}^2 - 2T_{n + 5}^2 + T_{n + \color{brown}6}^2 = 0\\[1mm] &T_n^3 - 2T_{n + 1}^3 + 2T_{n + 2}^3 - T_{n + 3}^3 - 14T_{n + 4}^3 \;\;+\;\; \dots \;\;+\;\; T_{n + \color{brown}{10}}^3 = 0\\ \end{aligned}$$

Notice that $3,6,10$ (and next is $15$) are generated by $m=\tfrac{1}{2}(k+1)(k+2)$.

III. Question:

Given a linear recurrence of order $d$,

$$s_n = a_1s_{n-1}+a_2s_{n-2}+\dots+a_ds_{n-d}$$

with $a_d\neq0$. Assume one can find a formula valid for all positive integer $n$,

$$c_0s_n^k+c_1s_{n+1}^k+c_2s_{n+2}^k+\dots+c_{m}s_{n+m}^k=0$$

with integer $c_i$ and positive integer $k$. How do we show that the required $m$ is a function of $k$ (and $d$) and in fact is a figurate number? Hence,

$$\begin{array}{|c|c|c|} \hline \text{Order}\; d&m&\text{Name}\\ \hline 2&k+1&\text{linear}\\ \hline 3&\tfrac{1}{2}(k+1)(k+2)&\text{triangular numbers}\\ \hline 4&\tfrac{1}{6}(k+1)(k+2)(k+3)&\text{tetrahedral numbers}\\ \hline \end{array}$$

P.S. I tested it with the Padovan sequence $P_n = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9,\dots$ (and others with 3rd order) and it has the same pattern,

$$\begin{aligned} &P_n+P_{n+1}-P_{n+\color{brown}3}=0\\[1mm] &P_n^2 - P_{n + 1}^2 + P_{n + 2}^2 - P_{n + 3}^2 - P_{n + 4}^2 - P_{n + 5}^2 + P_{n + \color{brown}6}^2 = 0\\ \end{aligned}$$

and so on. I also tested the tetranacci sequence and for $k = 1,2,3$ we have $m=4,10,20$ which are the first tetrahedral numbers.

Answer 1

Caveat: this is more a sketch of a possible approach than a complete answer.

Given a general linear recurrence $x_n = a_1 x_{n-1} + \ldots + a_r x_{n-r}$ the solution is typically of the form $x_n = \alpha_1 \beta_1{}^n + \ldots + \alpha_r \beta_r{}^n$.

So if we consider $$x_n^k = (\alpha_1 \beta_1{}^n + \ldots + \alpha_r \beta_r{}^n)^k = \sum_{\lambda \,\vdash\, k} A_\lambda \left(\beta_1{}^{\lambda_1}\ldots \beta_r{}^{\lambda_r}\right)^n$$(where $\lambda \,\vdash\, k$ means that $\lambda$ is a partition of $k$, and the formulation of $A_\lambda$ in terms of the $\alpha_i$ is left as an exercise) we see that we can expect it to satisfy a linear recurrence.

Gaps in the argument:

1. I haven't covered the case where the characteristic polynomial of the original recurrence has repeated roots. I think this gap can be filled because that gives terms $\alpha_i x^j \beta_i^x$ which carry through to give similar terms in the new recurrence.
2. I haven't argued for the order of the derived recurrence.

Answer 2

Here's a way of phrasing Peter's proof that I think makes it less bookkeeping-intensive:

• Define the Hadamard product of two sequences $\{a_n\}$, $\{b_n\}$ to be the sequence $\{a_n b_n\}$.
• Note that the vector space of sequences forms an algebra under Hadamard product (that is, it distributes over ordinary addition and is compatible with ordinary scalar multiplication).
• Call a sequence simple if it is of the form $\{n^k \alpha^n\}$ for some constants $k,\alpha$.
• Note that the Hadamard product of simple sequences is simple.
• Note that a sequence is the solution to a constant-coefficient linear recurrence relation if and only if it is a linear combination of simple sequences.
• Conclude that the Hadamard product of two such solutions is also the solution to a constant-coefficient linear recurrence relation.
• Induct!

Alternately, see these notes for another perspective...