Rational Generating Functions

I noticed that the number associated with my diurnal age today can be generated from the expansion of:$$ \frac{1-x}{1-x-x^2-2x^3+2x^4} $$I also noticed there is an associated fourth order linear recurrence:$$ \begin{align} &\text{a}(n) = \text{a}(n-1) + \text{a}(n-2) + 2\text{a}(n-3) - 2\text{a}(n-4) \\ &\text{with } \text{a}(0)=1, \text{a}(1)=0, \text{a}(2)=1, \text{a}(3)=3 \end{align} $$Having just posted about converting polynomials to linear recurrences, I was curious as to how to could be done for rational expressions involving two polynomials, one the numerator and the other the denominator. I asked Gemini the following:

Can expressions like \( \dfrac{1-x}{1-x-x^2-2x^3+2x^4} \) which are not polynomials still be expressed as fourth order linear recurrences and if so, how that be accomplished using this expression as an example.

Here was the response:

Yes, expressions like this can absolutely be expressed as linear recurrences. In mathematics, an expression in the form of a ratio of two polynomials is known as a rational generating function.

The sequence of coefficients generated by expanding this fraction directly corresponds to a linear recurrence relation. Specifically:

• The denominator dictates the recurrence relation itself (the multipliers and the order).
• The numerator determines the initial conditions (the starting values of the sequence).

Here is the complete step-by-step breakdown of how to extract the fourth-order linear recurrence and its initial conditions from your specific example.

1. Set Up the Generating Function Equation

Let the rational expression equal a formal power series, where $a_n$ represents the $n$-th term of the sequence we want to find:

$$\sum_{n=0}^{\infty} a_n x^n = \frac{1-x}{1-x-x^2-2x^3+2x^4}$$

2. Isolate the Sequence

To relate the coefficients, multiply both sides of the equation by the denominator:

$$(1-x-x^2-2x^3+2x^4) \sum_{n=0}^{\infty} a_n x^n = 1-x$$

Next, expand the left side by distributing the sequence across the terms of the polynomial. This creates shifted versions of the sequence:

$$\sum_{n=0}^{\infty} a_n x^n - \sum_{n=0}^{\infty} a_n x^{n+1} - \sum_{n=0}^{\infty} a_n x^{n+2} - 2\sum_{n=0}^{\infty} a_n x^{n+3} + 2\sum_{n=0}^{\infty} a_n x^{n+4} = 1-x$$

3. Extract the Recurrence Relation

To find the general recurrence relation, look at the coefficient of $x^n$ for any $n \ge 4$. On the right side of the equation ($1-x$), there are no terms with $x^4$ or higher, so the coefficient for $x^n$ on the right side is 0.

Equating the coefficients of $x^n$ on both sides gives:

$$a_n - a_{n-1} - a_{n-2} - 2a_{n-3} + 2a_{n-4} = 0$$

By isolating $a_n$, we get the fourth-order linear recurrence:

$$a_n = a_{n-1} + a_{n-2} + 2a_{n-3} - 2a_{n-4}$$

4. Determine the Initial Conditions

To compute the sequence, we need the first four values ($a_0, a_1, a_2, a_3$). We find these by equating the coefficients for the lowest powers of $x$ ($x^0, x^1, x^2, x^3$) on both sides of our expanded equation.

• For $x^0$ (constant term):
  $a_0 = 1$
  
  
• For $x^1$: 
  $a_1 - a_0 = -1 \implies a_1 - 1 = -1 \implies a_1 = 0$
  
  
• For $x^2$: 
  $a_2 - a_1 - a_0 = 0 \implies a_2 - 0 - 1 = 0 \implies a_2 = 1$
  
  
• For $x^3$: 
  $a_3 - a_2 - a_1 - 2a_0 = 0 \implies a_3 - 1 - 0 - 2(1) = 0 \implies a_3 = 3$

The recurrence sequence is fully defined by $a_n = a_{n-1} + a_{n-2} + 2a_{n-3} - 2a_{n-4}$ with initial conditions $\{1, 0, 1, 3\}$.

Palindrome 28082

Figure 1: Gemini Generated

Figure 1 depicts the number associated with my diurnal age today: the palindromic cyclops number \( \textbf{28082}\). I quite like the depiction. The previous such number, 27072, occurred on the 18th May 2023 and I celebrated its occurrence with a post titled Another Palindromic Cyclops Number. Prior to this, I was 26062 days old on the 10th August 2020 and again I created a post, titled Palindromic Cyclops Numbers. These numbers occur every 1010 days except when the transition involves a new leading digit. For example, following 29092, the next palindromic cyclops number is 30003 and the two are only separated by 11 days.

The number 28082 has no outstanding or unusual properties and so in this post I'm only celebrating it in terms of it being another base 10 milestone. After repeated failures using Nano Bananas, Gemini offered to implement the graphic shown in Figure 2 using Python code. There are 28 letters in the phrase "TWENTY EIGHT THOUSAND EIGHTY TWO" and the graphic depicts this. The number in digit format consists of 28, a central 0 and then 28 reversed. There are also 28 days in this current month of February. Today is the 20th of February and the digit sum of 28082 is 20.

Figure 2: permalink

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

Birthday Digits

Gemini's Infographic Summary of the Content in this Post

I recently turned 28077 days old and with my 77th birthday rapidly approaching I wondered if it's possible for a person's birthday to fall in such a way that their age in years matched the last two digits of their diurnal age. I prompted Gemini:

Suppose someone is born on April 3rd 1949. Let's count this as day 0. April 4th 1949 then counts as day 1 and so on. This progressive number we term the person's diurnal age as opposed to their age in years. As the person ages (let's say from 1 to 100) is there a birthday such that the last two digits of their diurnal age equals their age in years. Can you write a program in SageMath to determine this. The program should run in SageMathCell or a Jupyter notework.

The program (permalink) came up with only one age, 14, and an associated diurnal age of 5114 for person's born within a certain date range. For example for persons born in 2012 who are turning 14 this year (2026), only those with birthdates between the 1st January and 28th February will satisfy. Let's check for somebody turning 14 today (16th February 2026) using Wolfram Alpha. See Figure 1.

Figure 1

As can be seen, someone turning 14 years old today will be 5114 days old, satisfying the requirement. I queried Gemini as to whether there might be ages other than 14 that satisfy and this was the response:

Yes, I am sure. Age 14 is the only age in a normal human lifespan (1–100+) where this mathematical coincidence occurs. We can prove this by checking the mathematical constraints for every single age.

The Logic: Why it's only 14

For a match to happen at Age $N$, the following equation must be true: $$(64 \times N) + \text{Leap Days} \quad \text{must be divisible by } 100$$

At Age 14: $64 \times 14 = 896$. The remainder is 96. To reach the next 100, we need 4 more. Can a 14-year-old have lived through 4 leap days? Yes (e.g., born Jan 1948). Result: Match.

At Age 39 (The next closest candidate): $64 \times 39 = 2496$. The remainder is 96. To reach the next 100, we again need 4 more. Can a 39-year-old have lived through only 4 leap days? No. In 39 years, you must experience 9 or 10 leap years. Result: Impossible.

Gemini also explained it earlier in a slightly different way so I'll include that here:

The Math Behind the Age 14 Match

For a match to occur, we need: $$\text{Total Days} \pmod{100} = \text{Age}$$

Let's look at Age 14:

Standard Days: $14 \text{ years} \times 365 \text{ days/year} = 5110 \text{ days}$.

The Remainder: $5110 \pmod{100} = 10$.

The Gap: The remainder is 10, but we need it to equal the age, 14.

The Solution: We need exactly 4 extra days (leap days) to bridge the gap from 10 to 14 ($5110 + 4 = 5114$).

Therefore, any person who experiences exactly 4 leap years by their 14th birthday will have a diurnal age of 5114. Since 5114 ends in 14, this is a perfect match.

Why April 3, 1949 Misses the Match

Let's apply this to your specific date: April 3, 1949.

Period: April 3, 1949 to April 3, 1963.

Leap Years Encountered: 1952, 1956, 1960.

Total Leap Days: 3.

Total Diurnal Age: $5110 + 3 = 5113$.

Result: $5113$ ends in 13. The age is 14. (Missed by 1 day).

Who Gets the Match?

To get 4 leap days in 14 years, you must be born just before a leap day, so that you catch the first one immediately, and then three more over the next 12 years.

This generally happens to people born in January or February of a Leap Year (or late in the year prior to a leap year).

Fibonacci From Prime Factors

Gemini's Infographic Summary of the Content in this Post

I noticed that the number (\( \textbf{28075} \)) associated with my diurnal age today has an interesting property relating to its prime factors:$$28075=5^2 \times 1123$$The number has distinct prime factors of \( \textbf{5}\) and \( \textbf{1123}\). If these two factors are written in reversed order and then concatenated, the number \( \textbf{11235}\) is formed with digits that form a Fibonacci sequence:$$1+1 \rightarrow 2 \text{ and } 2 + 3 \rightarrow 5$$This got me thinking about what other numbers have this property and so I set Gemini to work to find all such numbers in the range from 1 to 40000. It turns out that the following numbers qualify (permalink):

22, 26, 30, 44, 52, 60, 66, 70, 88, 90, 101, 104, 115, 120, 132, 140, 141, 150, 158, 167, 176, 180, 198, 203, 205, 208, 210, 240, 242, 253, 257, 264, 270, 280, 300, 301, 316, 330, 338, 347, 350, 352, 360, 396, 416, 420, 423, 427, 450, 480, 484, 490, 528, 540, 560, 575, 594, 600, 611, 617, 630, 632, 660, 676, 700, 704, 720, 726, 750, 771, 790, 792, 810, 832, 835, 840, 900, 960, 968, 980, 990, 1025, 1050, 1056, 1080, 1120, 1123, 1188, 1200, 1222, 1260, 1264, 1265, 1269, 1320, 1350, 1352, 1400, 1408, 1421, 1440, 1452, 1459, 1470, 1500, 1580, 1584, 1620, 1650, 1664, 1680, 1750, 1782, 1800, 1890, 1920, 1936, 1960, 1980, 2100, 2107, 2112, 2160, 2178, 2240, 2250, 2313, 2376, 2400, 2430, 2444, 2450, 2520, 2528, 2640, 2645, 2662, 2700, 2704, 2783, 2800, 2816, 2875, 2880, 2904, 2940, 2970, 2989, 3000, 3150, 3160, 3168, 3240, 3257, 3300, 3328, 3360, 3430, 3500, 3564, 3600, 3630, 3750, 3780, 3807, 3840, 3872, 3920, 3950, 3960, 4050, 4175, 4200, 4224, 4320, 4356, 4377, 4394, 4410, 4480, 4500, 4752, 4800, 4860, 4888, 4900, 4950, 5040, 5056, 5125, 5167, 5250, 5279, 5280, 5324, 5346, 5400, 5408, 5600, 5615, 5632, 5670, 5760, 5808, 5819, 5880, 5887, 5940, 6000, 6300, 6319, 6320, 6325, 6336, 6480, 6534, 6600, 6627, 6656, 6720, 6750, 6860, 6939, 7000, 7128, 7200, 7260, 7290, 7350, 7500, 7560, 7680, 7744, 7840, 7900, 7920, 7943, 7986, 8100, 8250, 8400, 8405, 8448, 8640, 8712, 8750, 8788, 8820, 8910, 8960, 9000, 9450, 9504, 9600, 9720, 9776, 9800, 9900, 9947, 10080, 10112, 10201, 10290, 10500, 10560, 10648, 10692, 10800, 10816, 10890, 11200, 11250, 11264, 11340, 11421, 11520, 11616, 11760, 11880, 12000, 12150, 12250, 12482, 12600, 12640, 12672, 12943, 12960, 13068, 13131, 13200, 13225, 13230, 13312, 13440, 13500, 13720, 13915, 14000, 14256, 14375, 14400, 14520, 14580, 14700, 14749, 14850, 15000, 15120, 15360, 15488, 15680, 15750, 15800, 15840, 15886, 15972, 16038, 16200, 16500, 16800, 16896, 17010, 17150, 17280, 17424, 17500, 17576, 17640, 17820, 17920, 18000, 18150, 18750, 18900, 19008, 19200, 19440, 19552, 19600, 19602, 19750, 19800, 19881, 20160, 20224, 20250, 20580, 20817, 20875, 20923, 21000, 21120, 21296, 21347, 21384, 21600, 21632, 21780, 21870, 22050, 22400, 22500, 22528, 22680, 23040, 23232, 23520, 23760, 23958, 24000, 24010, 24300, 24500, 24750, 24964, 25200, 25280, 25344, 25625, 25920, 26047, 26136, 26250, 26400, 26460, 26624, 26730, 26880, 27000, 27440, 27889, 28000, 28075, 28350, 28512, 28717, 28800, 29040, 29095, 29160, 29282, 29400, 29700, 30000, 30240, 30613, 30720, 30870, 30976, 31360, 31500, 31600, 31625, 31680, 31772, 31944, 32076, 32400, 32670, 33000, 33600, 33750, 33792, 34020, 34263, 34300, 34560, 34848, 35000, 35152, 35280, 35640, 35840, 36000, 36300, 36450, 36750, 37500, 37800, 38016, 38400, 38880, 39104, 39200, 39204, 39393, 39500, 39600, 39690, 39930

Of course looking at these numbers it's not immediately apparent what the Fibonacci digit sequence is but the Gemini program creates a table to show this. I'll restrict the range to between 28000 and 29000. The result is shown in Figure 1:

Figure 1: permalink

The fact that we are only considering \( \textbf{distinct} \) prime factors helps the program run quickly and there are no problems using it with SageMathCell. However if we allow multiplicity of factors, the number of permutations increases dramatically and SageMathCell quickly times out even if we restrict the range to between 28000 and 29000. So I think working only with distinct prime factors is the way to go.

Generating Functions

Only yesterday in a post titled Linear Recurrence Revisited did I look at this recurrence in relation to my diurnal age of 28072:$$ \begin{align} &\text{a}(n+3) = 2\text{a}(n+2) - 3\text{a}(n+1) + 2\text{a}(n)\\ & \text{a}(0) = 1, \text{a}(1) = 1, \text{a}(2) = 0 \end{align}$$Today, a day later, I find that 28073 can also be linked to a linear recurrence via OEIS A157651:$$ \begin{align} &\text{a}(n) = 3\text{a}(n-1) -3\text{a}(n-2) +\text{a}(n-3) \\ &\text{a}(0) =57, \text{a}(1) =308, \text{a}(3)=759 \end{align}$$The initial terms are:

57, 308, 759, 1410, 2261, 3312, 4563, 6014, 7665, 9516, 11567, 13818, 16269, 18920, 21771, 24822, 28073, 31524, 35175, 39026, 43077, 47328, 51779, 56430, 61281, 66332, 71583, 77034, 82685, 88536, 94587, 100838, 107289, 113940, 120791, 127842

However, this time I want to look at ordinary generating functions and exponential generating functions in relation to this linear recurrence. The following was created by Gemini.

$$
\begin{array}{@{}l}



\textbf{Derivation of the Ordinary Generating Function } G(x) \\[12pt]


\text{Let } G(x) = \displaystyle\sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots \\[12pt]
\text{The recurrence relation is: } a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0 \text{ for } n \ge 3. \\[12pt]


\text{We multiply } G(x) \text{ by the polynomial } (1 - 3x + 3x^2 - x^3): \\[6pt]
(1 - 3x + 3x^2 - x^3)G(x) = \\[6pt]
\quad \phantom{-} (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots) \\
\quad - \displaystyle 3x (a_0 + a_1 x + a_2 x^2 + \dots) \\
\quad + \displaystyle 3x^2 (a_0 + a_1 x + \dots) \\
\quad - \displaystyle x^3 (a_0 + \dots) \\[18pt]


\text{Grouping coefficients by powers of } x: \\[6pt]
\text{Constant: } a_0 = 57 \\[6pt]
x^1: a_1 - 3a_0 = 308 - 3(57) = 308 - 171 = 137 \\[6pt]
x^2: a_2 - 3a_1 + 3a_0 = 759 - 3(308) + 3(57) = 759 - 924 + 171 = 6 \\[6pt]
x^n \text{ (for } n \ge 3\text{): } a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0 \\[18pt]


\text{Thus:} \\[6pt]
(1 - x)^3 G(x) = 57 + 137x + 6x^2 \\[12pt]


\text{The Ordinary Generating Function is:} \\[6pt]
G(x) = \displaystyle\frac{57 + 137x + 6x^2}{(1 - x)^3} \\[24pt]




\textbf{Derivation of the Exponential Generating Function } E(x) \\[12pt]


\text{Let } E(x) = \displaystyle\sum_{n=0}^{\infty} a_n \frac{x^n}{n!}. \\[12pt]
\text{The recurrence } a_n - 3a_{n-1} + 3a_{n-2} - a_{n-3} = 0 \\ \text{ becomes the differential equation:} \\[6pt]
E'''(x) - 3E''(x) + 3E'(x) - E(x) = 0 \\[12pt]


\text{The characteristic equation is } r^3 - 3r^2 + 3r - 1 = (r-1)^3 = 0. \\[6pt]
\text{This has a triple root at } r = 1. \\[12pt]


\text{The general solution for a triple root is:} \\[6pt]
E(x) = (C_1 + C_2 x + C_3 x^2)e^x \\[12pt]


\text{We find constants } C_1, C_2, C_3 \text{ using initial conditions } a_0=57, a_1=308, a_2=759. \\[6pt]
\text{Note that } a_n \text{ is the coefficient of } \frac{x^n}{n!}. \\[6pt]
\text{Expanding } E(x) = (C_1 + C_2 x + C_3 x^2) \displaystyle \sum \frac{x^n}{n!} \\ \text{ allows us to match coefficients directly.} \\[18pt]


\text{Solving for the constants (via derivatives at } x=0 \text{):} \\[6pt]
1. \quad E(0) = a_0 \implies C_1 = 57 \\[6pt]
2. \quad E'(0) = a_1 \implies C_1 + C_2 = 308 \implies 57 + C_2 = 308 \implies C_2 = 251 \\[6pt]
3. \quad E''(0) = a_2 \implies C_1 + 2C_2 + 2C_3 = 759 \\[6pt]
\phantom{3. \quad} 57 + 2(251) + 2C_3 = 759 \\[6pt]
\phantom{3. \quad} 559 + 2C_3 = 759 \implies 2C_3 = 200 \implies C_3 = 100 \\[18pt]


\text{The Exponential Generating Function is:} \\[6pt]
E(x) = (57 + 251x + 100x^2)e^x \\[24pt]




\textbf{Expansion of the Ordinary Generating Function} \\[12pt]


\text{The correct OGF is: } G(x) = \displaystyle\frac{57 + 137x + 6x^2}{(1-x)^3} \\[12pt]


\text{We use the binomial series expansion for } (1-x)^{-3}: \\[6pt]
(1-x)^{-3} = \displaystyle\sum_{n=0}^{\infty} \binom{n+2}{2} x^n = \displaystyle\sum_{n=0}^{\infty} \frac{(n+1)(n+2)}{2} x^n \\[12pt]


\text{Multiply this series by the numerator } (57 + 137x + 6x^2): \\[6pt]
a_n = 57 \cdot \binom{n+2}{2} + 137 \cdot \binom{n+1}{2} + 6 \cdot \binom{n}{2} \\[12pt]


\text{Let's verify the first few terms again with the correct formula:} \\[12pt]


\textbf{For } n=0: \\[6pt]
a_0 = 57 \cdot \frac{(1)(2)}{2} = 57(1) = \mathbf{57} \\[12pt]


\textbf{For } n=1: \\[6pt]
\text{The term } \binom{n}{2} \text{ is 0 for } n < 2. \\[6pt]
a_1 = 57 \cdot \frac{(2)(3)}{2} + 137 \cdot \frac{(1)(2)}{2} \\[6pt]
a_1 = 57(3) + 137(1) = 171 + 137 = \mathbf{308} \\[12pt]


\textbf{For } n=2: \\[6pt]
a_2 = 57 \cdot \frac{(3)(4)}{2} + 137 \cdot \frac{(2)(3)}{2} + 6 \cdot \frac{(2)(1)}{2} \\[6pt]
a_2 = 57(6) + 137(3) + 6(1) \\[6pt]
a_2 = 342 + 411 + 6 = \mathbf{759} \\[12pt]


\textbf{For } n=3: \\[6pt]
a_3 = 57 \cdot \frac{(4)(5)}{2} + 137 \cdot \frac{(3)(4)}{2} + 6 \cdot \frac{(3)(2)}{2} \\[6pt]
a_3 = 57(10) + 137(6) + 6(3) \\[6pt]
a_3 = 570 + 822 + 18 = \mathbf{1410} \\[24pt]




\textbf{Expansion of the Exponential Generating Function} \\[12pt]


\text{We expand } e^x = \displaystyle\sum_{n=0}^{\infty} \dfrac{x^n}{n!} = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \dots \\[12pt]


\text{Multiply by the polynomial } (57 + 251x + 100x^2): \\[6pt]
E(x) = 57 \displaystyle\sum \dfrac{x^n}{n!} + 251x \displaystyle\sum \dfrac{x^n}{n!} + 100x^2 \displaystyle\sum \dfrac{x^n}{n!} \\[12pt]


\text{To find } a_n, \text{ we look for the coefficient of } \frac{x^n}{n!} \text{ in the combined sum.} \\[6pt]
\text{Note that } x \cdot \dfrac{x^{n-1}}{(n-1)!} = n \dfrac{x^n}{n!} \text{ and } x^2 \cdot \dfrac{x^{n-2}}{(n-2)!} = n(n-1) \dfrac{x^n}{n!}. \\[12pt]


\text{This gives us the direct formula:} \\[6pt]
a_n = 57(1) + 251(n) + 100(n)(n-1) \\[6pt]
a_n = 100n^2 + 151n + 57 \\[12pt]


\text{Let's calculate the terms using this formula:} \\[12pt]


\textbf{For } n=0: \\[6pt]
a_0 = 0 + 0 + 57 = \mathbf{57} \\[12pt]


\textbf{For } n=1: \\[6pt]
a_1 = 100(1) + 151(1) + 57 = 251 + 57 = \mathbf{308} \\[12pt]


\textbf{For } n=2: \\[6pt]
a_2 = 100(4) + 151(2) + 57 = 400 + 302 + 57 = \mathbf{759} \\[12pt]


\textbf{For } n=3: \\[6pt]
a_3 = 100(9) + 151(3) + 57 = 900 + 453 + 57 = \mathbf{1410}
\end{array}
$$

I prefer to work with the ordinary generating function in which case the following simple code will generate the terms:

Linear Recurrence Revisited

It's been a while since I posted about linear recurrence relations. The only two posts were:

• Solving Linear Recurrence on the 16th of June 2020
  
• More on Linear Recurrence on the 26th December 2020

Today I turned \(28073\) days old and one of the properties of this number is that it's a member of OEIS A105578:$$ \begin{align}  &\text{a}(n+3) = 2\text{a}(n+2) - 3\text{a}(n+1) + 2\text{a}(n)\\ &a(0) = 1, a(1) = 1, a(2) = 0 \end{align}$$This linear recurrence of order 3 corresponds to the cubic equation:$$ \begin{align} &x^3 = 2x^2 -3x +2 \\ &x^3-2x^2+3x-2 = 0 \end{align}$$The polynomial \( \text{P}(x) = x^3-2x^2+3x-2 \) has three roots, one real (at \(x=1\) ) and two complex. See Figure 1.

Figure 1

The roots are:

• \( x_1=1 \)
• \( x_2 = \dfrac{1}{2}(1-i \sqrt{7}) \)
• \( x_3 = \dfrac{1}{2}(1+i \sqrt{7}) \)

These roots can be used to find any term in the sequence because of the following relationship:$$a_n=A(x_1)^n+B(x_2)^n+C(x_3)^n \text{ with A, B and C constants}$$Substituting the initial conditions we get three equations in three unknowns:$$ \begin{align} A + B + C &= 1 \\ Ax_1+Bx_2+Cx_3 &=1 \\ A(x_1)^2+B(x_2)^2+C(x_3)^2 &=0 \end{align} $$In terms of the roots, the values for \( A, B \text{ and } C \) are:$$ \begin{align} A = \frac{x_1 - x_2 x_3 - (x_2 + x_3)}{(x_1 - x_2)(x_1 - x_3)} \\ B = \frac{x_2 - x_1 x_3 - (x_1 + x_3)}{(x_2 - x_1)(x_2 - x_3)} \\ C = \frac{x_3 - x_1 x_2 - (x_1 + x_2)}{(x_3 - x_1)(x_3 - x_2)} \end{align} $$We know that when \(n=32\), the term is 28072 (my diurnal age) so let's check if that works by substituting the values of \( x_1,x_2 \text{ and } x_3 \) into and summarising at the same time what we've found previously:$$
\begin{array}{l}
\textbf{Step 1: Determine the Roots of the Characteristic Equation} \\[6pt]
x^3 - 2x^2 + 3x - 2 = 0 \\[4pt]
(x-1)(x^2 - x + 2) = 0 \\[4pt]
\text{The roots are:} \\[4pt]
x_1 = 1 \\[4pt]
x_2 = \dfrac{1 + i\sqrt{7}}{2} \\[4pt]
x_3 = \dfrac{1 - i\sqrt{7}}{2} \\[18pt]


\textbf{Step 2: Find Constants A, B, and C} \\[6pt]
\text{Using the initial conditions } a_0=1, a_1=1, a_2=0: \\[6pt]
A = \dfrac{1}{2} \\[6pt]
B = \dfrac{1}{4} - \dfrac{i}{4\sqrt{7}} \\[6pt]
C = \dfrac{1}{4} + \dfrac{i}{4\sqrt{7}} \\[18pt]


\textbf{Step 3: Construct the Explicit Formula} \\[6pt]
a_n = A(x_1)^n + B(x_2)^n + C(x_3)^n \\[6pt]
a_n = \dfrac{1}{2}(1)^n + \left(\dfrac{1}{4} - \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 + i\sqrt{7}}{2}\right)^n + \left(\dfrac{1}{4} + \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 - i\sqrt{7}}{2}\right)^n \\[18pt]


\textbf{Step 4: Verify for } n=32 \text{ (Detailed Breakdown)} \\[12pt] \text{We need to sum three terms: } \\[4pt] a_{32} = \underbrace{A(x_1)^{32}}_{\text{Term 1}} + \underbrace{B(x_2)^{32}}_{\text{Term 2}} + \underbrace{C(x_3)^{32}}_{\text{Term 3}} \\[18pt] \textbf{1. Calculate Term 1 (The Real Root)} \\[6pt] \text{Since } x_1 = 1 \text{ and } A = 0.5: \\[6pt] \text{Term 1} = 0.5 \cdot (1)^{32} = \mathbf{0.5} \\[18pt] \textbf{2. Calculate Terms 2 and 3 (The Complex Roots)} \\[6pt] \text{Notice that } C \text{ is the complex conjugate of } B, \text{ and } x_3 \text{ is the conjugate of } x_2. \\[6pt] \text{This implies that Term 3 is the complex conjugate of Term 2.} \\[6pt] \text{Mathematical Rule: } Z + \bar{Z} = 2 \cdot \text{RealPart}(Z). \\[6pt] \text{Therefore, we only need to calculate Term 2 and double its real component.} \\[12pt] \text{Let } x_2 = \sqrt{2}e^{i\theta} \text{ (Polar form, where } \sqrt{2} \text{ is the magnitude)}. \\[6pt] (x_2)^{32} = (\sqrt{2})^{32} e^{i32\theta} = 2^{16} (\cos(32\theta) + i\sin(32\theta)) \\[6pt] (x_2)^{32} = 65536 (\cos(32\theta) + i\sin(32\theta)) \\[12pt] \text{When we multiply this by } B \text{ and take } 2 \times \text{Real Part, the result is exactly:} \\[6pt] \text{Term 2} + \text{Term 3} = \mathbf{28071.5} \\[18pt] \textbf{3. Final Total} \\[6pt] a_{32} = \text{Term 1} + (\text{Terms 2 \& 3}) \\[6pt] a_{32} = 0.5 + 28071.5 \\[6pt] a_{32} = \mathbf{28072} \end{array} $$

Getting back to OEIS A105578, a plot of the first 52 members is show in Figure 2:

1, 1, 0, -1, 0, 3, 4, -1, -8, -5, 12, 23, 0, -45, -44, 47, 136, 43, -228, -313, 144, 771, 484, -1057, -2024, 91, 4140, 3959, -4320, -12237, -3596, 20879, 28072, -13685, -69828, -42457, 97200, 182115, -12284, -376513, -351944, 401083, 1104972, 302807, -1907136, -2512749, 1301524, 6327023, 3723976, -8930069, -16378020, 1482119, 34238160, 31273923, -37202396

Figure 2: permalink

It can be seen that after a while the values between to fluctuate wildly between larger and larger positive and negative values.

There is a database for a great many linear recurrences of order 3 listed here.