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\}$.