Of fibonomials, pellonomials, and tribonomials, etc

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.

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.
• I've generalized my question. I guess the hard part is to show what is the required value of $m$. (I've empirically observed they are figurate numbers where the variables are in terms of $k$.) – Tito Piezas III Feb 5 '15 at 0:36
• As a disclaimer, I only tested sequences where the characteristic polynomial has no repeated roots, so I don't know how valid my observations are (especially $m$ being a figurate number) if we include the case with repeated roots. – Tito Piezas III Feb 5 '15 at 0:50
• @TitoPiezasIII, I would guess that being figurate numbers is a consequence of the figurate numbers being binomials; I can see how binomial numbers might be related to the number of different values of $\prod_i\beta_i{}^{\lambda_i}$ in the case that the $\beta_i$ are sufficiently independent. – Peter Taylor Feb 5 '15 at 8:17

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...

• I've generalized the question. Is it possible to tweak your answer to derive the variable $m$? (Kindly see my comment to Peter's post.) – Tito Piezas III Feb 5 '15 at 0:41
• @TitoPiezasIII: Short answer before I run off to dinner, which I'll probably update later: you can certainly use it to derive an upper bound for $m$, which will be the correct value in almost all cases. However there's the possibility of numerical coincidences. A possibly instructive example is given by the sequence $\{4^n+6^n+9^n\}$, which satisfies an order-3 recurrence and whose square satisfies an order-5 recurrence. – Micah Feb 5 '15 at 1:05