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$,


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.
  • $\begingroup$ 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$.) $\endgroup$ Feb 5 '15 at 0:36
  • $\begingroup$ 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. $\endgroup$ Feb 5 '15 at 0:50
  • $\begingroup$ @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. $\endgroup$ 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...

  • $\begingroup$ 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.) $\endgroup$ Feb 5 '15 at 0:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – Micah
    Feb 5 '15 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.