From Polynomial to Linear Recurrence

I noticed that the number associated with my diurnal age today (28080) is a member of OEIS  A144459 formed from a quadratic polynomial:$$ \text{a}(n) = (3n+1)(5n+1) $$The initial members are:

1, 24, 77, 160, 273, 416, 589, 792, 1025, 1288, 1581, 1904, 2257, 2640, 3053, 3496, 3969, 4472, 5005, 5568, 6161, 6784, 7437, 8120, 8833, 9576, 10349, 11152, 11985, 12848, 13741, 14664, 15617, 16600, 17613, 18656, 19729, 20832, 21965, 23128, 24321, 25544, 26797, 28080

What interested me was that the sequence members could also be generated from a linear recurrence:$$ \begin{align} \text{a}(n) = 3\text{a}(n-1) -3\text{a}(n-2) +\text{a}(n-3) \\ \text{with } \text{a}(0)=1, \text{a}(1)=24 \text{ and } \text{a}(2)=77 \end{align}$$How do we get from \( \text{a}(n) = (3n+1)(5n+1) \text{ to } \text{a}(n-1) -3\text{a}(n-2) +\text{a}(n-3) \)? Gemini's response was a follows:

Deriving the Linear Recurrence for OEIS A144459

To derive the linear recurrence \(a(n) = 3a(n-1) - 3a(n-2) + a(n-3)\) from the explicit formula \(a(n) = (3n+1)(5n+1)\), we utilize the Method of Finite Differences.

This method relies on a fundamental rule of sequence algebra: Any sequence defined by a polynomial of degree \(d\) satisfies a linear recurrence relation of order \(d+1\) with binomial coefficients.

Step 1: Determine the Degree of the Polynomial

First, expand the explicit formula to see the structure of the polynomial:

$$ a(n) = (3n+1)(5n+1) $$ $$ a(n) = 15n^2 + 3n + 5n + 1 $$ $$ a(n) = 15n^2 + 8n + 1 $$

Since the highest power of \(n\) is 2, this is a quadratic polynomial (degree \(d=2\)).

Step 2: Apply the Difference Operator Rule

In the calculus of finite differences, we use the difference operator \(\Delta\). The rule states that if \(a(n)\) is a polynomial of degree 2:

• The first differences are linear (degree 1).
• The second differences are constant (degree 0).
• The third differences are exactly zero.

Mathematically, this means:

$$ \Delta^3 a(n) = 0 $$

Step 3: Expand using Shift Operators

We express the difference operator \(\Delta\) in terms of the shift operator \(E\), where \(E a(n) = a(n+1)\). We know that \(\Delta = E - 1\).

Since the third difference is zero, we substitute \((E-1)\) for \(\Delta\):

$$ (E - 1)^3 a(n) = 0 $$

Now, we expand the cubic term using standard binomial expansion:

$$ (E^3 - 3E^2 + 3E - 1) a(n) = 0 $$

Step 4: Apply the Operators to the Sequence

Distribute the operator \(a(n)\) across the expanded terms. Recall that \(E^k a(n) = a(n+k)\):

$$ a(n+3) - 3a(n+2) + 3a(n+1) - a(n) = 0 $$

To match the standard recurrence form (where the highest term is \(a(n)\)), we shift the indices down by 3 (replace \(n\) with \(n-3\)):

$$ a(n) - 3a(n-1) + 3a(n-2) - a(n-3) = 0 $$

Step 5: Rearrange to the Final Recurrence

Move the negative terms to the right side to isolate \(a(n)\):

$$ a(n) = 3a(n-1) - 3a(n-2) + a(n-3) $$

---

Verification

We verify this by checking the initial values given for A144459.

Explicit Formula: \(a(n) = 15n^2 + 8n + 1\)

• \(a(0) = 1\), \(a(1) = 24\), \(a(2) = 77\)

Recurrence Check for \(a(3)\):

$$ a(3) = 3(77) - 3(24) + 1 $$ $$ a(3) = 231 - 72 + 1 $$ $$ a(3) = 160 $$

This matches the explicit calculation \(15(3)^2 + 8(3) + 1 = 160\).