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\).
******************************
Here is another example just to reinforce what's been covered earlier.
1. The Transformation Process
To convert the polynomial closed form into a linear recurrence relation, we use the method of finite differences.
Since the polynomial \( a_n = 2n^2 + 6n + 1 \) is of degree \( d=2 \), the sequence has a constant second difference and a zero third difference.
Step 1: Set up the Difference Operator
We define the shift operator \( E \) such that \( E a_n = a_{n+1} \). The difference operator is \( \Delta = E - 1 \).
Because the degree is 2, the third difference is zero:
\[ \Delta^3 a_n = 0 \]
Step 2: Expand the Operator
Substitute \( \Delta = E - 1 \) and expand the cubic expression:
\[ (E - 1)^3 a_n = 0 \]
\[ (E^3 - 3E^2 + 3E - 1) a_n = 0 \]
Step 3: Apply the Shift Operator
Distributing the operator to \( a_n \) gives the recurrence relation in terms of forward shifts:
\[ a_{n+3} - 3a_{n+2} + 3a_{n+1} - a_n = 0 \]
Step 4: Final Linear Recurrence
To solve for the current term based on previous terms, we shift the indices down by 3 (replace \( n+3 \) with \( n \)):
\[ \boxed{ a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3} } \]
Initial Conditions:
We calculate the first three seeds using the original polynomial \( 2n^2 + 6n + 1 \):
- \( a_0 = 1 \)
- \( a_1 = 9 \)
- \( a_2 = 21 \)
2. Comparison and Verification
The table below compares the values generated by the closed form polynomial against the derived linear recurrence.
\[
\begin{array}{|c|c|c|c|}
\hline
\textbf{n} & \textbf{Closed Form} & \textbf{Recurrence} & \textbf{Match} \\
& (2n^2 + 6n + 1) & (3a_{n-1} - 3a_{n-2} + a_{n-3}) & \\
\hline
0 & 1 & 1 & \text{True} \\
\hline
1 & 9 & 9 & \text{True} \\
\hline
2 & 21 & 21 & \text{True} \\
\hline
3 & 37 & 37 & \text{True} \\
\hline
4 & 57 & 57 & \text{True} \\
\hline
5 & 81 & 81 & \text{True} \\
\hline
6 & 109 & 109 & \text{True} \\
\hline
7 & 141 & 141 & \text{True} \\
\hline
8 & 177 & 177 & \text{True} \\
\hline
9 & 217 & 217 & \text{True} \\
\hline
\end{array}
\]
