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

******************************

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} \]

Selfie Numbers

Today, I turned 25926 days old and was surprised to discover that this is a so-called selfie number. The article in which I discovered this fact began with this abstract which explains what is meant by the term:

Numbers represented by their own digits by certain operations are considered as selfie numbers. Some times they are called wild narcissistic numbers. There are many ways of representing selfie numbers. They can be represented in digit’s order, reverse order of digits, increasing and/or decreasing order of digits, etc. These can be obtained by use of basis operations along with factorial, squareroot, Fibonacci sequence, Triangular numbers, binomial coefficients, s-gonal values, centered polygonal numbers, etc. In this work, we have written selfie numbers by use of concatenation, along with factorial and square-root. The concatenation idea is used in a very simple way. The work is limited up to 5 digits. Work on higher digits shall be dealt elsewhere. Source.

I discovered that 25926 could be expressed as \((−2+5)!! \times C(9,2)+6\). This immediately caused me confusion because I'm use to treating !! as the double factorial in which case we have:$$(-2+5)!!=3!!=3 \times 1 = 3$$However, this produces \(3 \times 36 +6=124\) and so something is wrong. After typing 3!! into a Google search, I saw what was meant (see Figure 1):

Figure 1

So instead of 3!!=3, we have (3!)!=6!=720 and now \(720 \times 36+6\) does give 25926.

The title of the previously mentioned article is:

Concatenation-Type Selfie Numbers
With Factorial and Square-Root

The author of the article, Inder J. Taneja1, categorises the selfie numbers into the following types:

1 Crazy Representations

1.1 Selfie Numbers

2 Concatenation-Type Selfie Numbers

2.1 Sequential Representations
2.1.1 Both Ways
2.1.2 Digit’s Order
2.1.3 Reverse Order of Digits
2.2 Non Sequential Representations
2.2.1 Both Ways
2.2.2 Digit’s Order
2.2.3 Reverse Order of Digits

3 Number Patterns

4 Summary: Selfie Numbers

4.1 Factorial
4.2 Factorial and Square-Root
4.3 Fibonacci Sequence
4.4 Triangular Numbers
4.5 Binomial Coefficients
4.6 S-gonal numbers
4.7 Centered Polygonal Numbers

The author has written a previous paper (it is 161 pages in length) that begins with the following abstract:

Natural numbers from 0 to 11111 are written in terms of 1 to 9 in two different ways. The first one in increasing order of 1 to 9, and the second one in decreasing order. This is done by using the operations of addition, multiplication, subtraction, potentiation, and division. In both the situations there are no missing numbers, except one, i.e., 10958 in the increasing case.

The decreasing case can be written as 10958 = (9 + 8 × 7 × 65 + 4) × 3 − 2 + 1. However, if factorials and square roots are allowed, then more than one representation of the increasing case is possible. Here are two examples:$$10958 := 1+2+3!!+(−4+5!+6−7)×89$$ $$10958 := 1×2×(3!!−4!×(5+6)+7!−8−9)$$The author uses factorials and square roots, as well as additional elements, for his selfie numbers. One of those additional elements is concatenation defined as:$$a \parallel b := 10 \times a + b, a \in \mathbb{Z}, b \in \{ 0, 1, 2, 3, 4, 6, 7, 8, 9 \}$$At first I was confused by the := symbol but I discovered its significance:

It is borrowed from computer programming: it means that the item on the left hand side is being defined to be what is on the right hand side. For example, \(𝑦:=7𝑥+2\) means that \(𝑦\) is defined to be \(7𝑥+2\). This is different from, say, writing \(1=\sin^2 \theta +\cos^2 \theta \). Source.

As an example of its use we have:$$ 2 \parallel 3 := 2 \times 10 + 3 = 23$$$$5 \parallel 15 := 5 × 100 + 15 = 515$$$$ ((3 \times 3) \parallel 1)^2 \times 4:=91^2 \times 4 = 33124$$It is possible to reverse the order of the digits as in the following example:$$39304 := ((4 \parallel 03) − 9) ^3$$Sometimes numbers can be written sequentially both forwards and backwards as in the following example where the square root and factorial are used in addition to concatenation:$$30969 := ((3 + 0!) \parallel \sqrt{9}) \times 6! + 9 = 9 + 6! × ((\sqrt{9}+0!)\parallel 3)$$The author also makes use of the Fibonacci sequence defined as:$$ F(0) = 0, F(1) = 1, F(n + 1) = F(n) + F(n − 1), n ≥ 1$$Below is an example of a selfie number that makes use of the Fibonacci sequence values:$$834660 := (F(8 × 3) × F(4) + 6) × 6 + 0 = 0 + 6 × (6 + F(4) × F(3 × 8))$$The triangular numbers are also used and the general formula for these is:$$T(n) = 1 + 2 + 3 + ... = \frac{n + 1} {2} = C(n + 1, 2)$$Here is an example of a selfie number that makes use of Triangular numbers:$$99633 := 3 + (3 + T(T(6) + T(9))) × T(9)$$As we saw with the example of my daily number, binomial coefficients can be used as well as S-gonal numbers, defined by the following formula:$$P(n, s) := \frac{n \,(n − 1) \, (s − 2) }{2} + n, s > 2$$Here is an example of a selfie number that makes use of S-gonal numbers:$$53995 := (5! − P(9, \sqrt{9})) × 3!! − 5$$Lastly, the author makes use of centered polygonal numbers defined by the formula:$$K(n,t) := \frac{t \, n \, (n − 1)}{ 2} + 1, t > 2$$An example of a selfie number using such numbers is:$$59938 := K(8, 3!) + (\sqrt{9})!! + 9^5 $$There are plenty of examples in the aforementioned paper and, though the arithmetic involved is simply enough once it's displayed, one has to often marvel at the ingenuity required to create the elements in the first place.

Selfie numbers are similar to Friedman numbers except that in the latter the digits can be in any order. A number \(n\)  is a Friedman number if it can be obtained combining all its digits with the 5 arithmetic operations and concatenation (of digits, not of results). For example, 13125 is a Friedman number since it can be written as \(21\times 5^{3+1}\). An impressive example is the pandigital number 9108432576 that can be written as \(251^3 \times 4 \times 6 \times(7 + 8 + 9 + 0) \).