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

Celebrating 27720

It's not often that numbers as large as 27720 attract 632 entries in the Online Encycopedia of Integer Sequences (OEIS). By contrast, 27719 attracts 31 entries and 27721 attracts 27 entries. So what's so special about 27720?

Well, it has lots of interesting properties. Let's look at some of them. 

\( \textbf{PROPERTY 1} \)

The very first entry in the database is OEIS A002182:

A002182  Highly composite numbers: numbers \(n\) where d(\(n\)), the number of divisors of \(n\)  increases to a record.

The initial record holders, up to 40000, are as follows where we see 27720 is a member:

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720

Table 1 shows the details:

Table 1: permalink

\( \textbf{PROPERTY 2} \)

In a similar vein is OEIS A004394 where 27720 also features:

A004394    superabundant numbers: \(n\) such that \( \sigma(n)/n > \sigma(m)/m \) for all \( m < n\), \( \sigma(n)\) being A000203(n), the sum of the divisors of \(n\).

The initial members are as follows with most being the same as for OEIS A002182:

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 10080, 15120, 25200, 27720

Table 2 shows the details:

Table 2: permalink

\( \textbf{PROPERTY 3} \)

Another interesting property of the number arises from its appearance in the denominator of the progressive sum of the harmonic numbers. These denominators constitute OEIS A002805.

A002805    denominators of harmonic numbers \( \text{H}(n) =\displaystyle \sum_{i=1} ^n \dfrac{1}{i} \)

The first terms in the sequence are 1, 2, 6, 12, 60, 20, 140, 280, 2520, 2520, 27720, 27720. Table 3 shows the details.

Table 3: permalink

\( \textbf{PROPERTY 4} \)

The number also arises from a quite simple recurrence relation:

A052542     \( \text{a}(n) = 2 \times \text{a}(n-1) + \text{a}(n-2), \text{ with } \text{a}(0) = 1, \text{a}(1) = 2, \text{a}(2) = 4 \)

The initial members of the sequence are 1, 2, 4, 10, 24, 58, 140, 338, 816, 1970, 4756, 11482, 27720 (permalink).

\( \textbf{PROPERTY 5} \)

Since \(27720 = 2^3 \times 3^2 \times 5 \times 7 \times 11 \), it is 12 times the product of the primorial number \(2310 = 2 \times 3 \times 5 \times 7 \times 11 \) and this qualifies it for membership in OEIS A129912 because 12 is itself a product of primorials viz. 2 x 6.

A129912 numbers that are products of distinct primorial numbers (see A002110).

The initial members of the sequence (with the primorials themselves included) can be generated using this permalink:

1, 2, 6, 12, 30, 60, 180, 210, 360, 420, 1260, 2310, 2520, 4620, 6300, 12600, 13860, 27720, 30030, 37800

Initially I misinterpreted this sequence as meaning numbers that are multiples of primorials but this is not the case. Instead the multiples themselves must be products of primorials and this is far more restrictive.

Clark's Triangle

One of the properties of today's number 26618, that marks my diurnal age, is that it is a member of OEIS A100206: 

A100206

Row sums of Clark's triangle A046902: Clark's triangle: left border = 0 1 1 1..., right border = multiples of 6; other entries = sum of 2 entries above.

The setup is shown in Figure 1, although it is a mirror image of that described in OEIS A100206 because the borders are reversed. The significance of the \( (m-1)^2\) and the \(n^2\) will be explained shortly.

Figure 1: source

To quote from Figure 1's source:

Clark's triangle is a number triangle created by setting the vertex equal to 0, filling one diagonal with 1s, the other diagonal with multiples of an integer \(f\), and filling in the remaining entries by summing the elements on either side from one row above. Figure 1 above shows Clark's triangle for \(f\)=6.

Call the first column \(n\)=0 and the last column \(m=n\) so that:

$$\begin{align} c_{m \, \scriptsize{0}} &= f\,m\\
c_{m\,m} &= 1 \end{align}$$then use the recurrence relation$$c_{m\,n}=c_{m-\scriptsize{1}, \,\normalsize{n}-\scriptsize{1}}+c_{m-\scriptsize{1}, \,\normalsize{n}}$$to compute the rest of the entries. The result is given analytically by$$c_{m\,n}=f \times \binom{m} {n+1}+\binom{m-1}{n-1}$$where \( \binom{n}{k} \) is a binomial coefficient.

The interesting part is that if \(f\)=6 is chosen as the integer, then 

\( c_{m \, \scriptsize{2}} \) and \(c_{m \, \scriptsize{3}}\) simplify to$$ \begin{align} c_{m \, \scriptsize{2}} &= (m-1)^3\\c_{m \, \scriptsize{3}} &= \dfrac{(m-1)^2(m-2)^2}{4} \end{align}$$which are consecutive cubes \( (m-1)^3 \) and nonconsecutive squares$$n^2=\left ( \dfrac{(m-1)(m-2)}{2} \right )^2$$The sum of the \(m\)-th row for \(m>0\) is given by$$ \sum_{n=0}^{m} c_{m\,n}=2^{m-1}+f \times (2^{m}-1) $$ (M. Alekseyev, pers. comm., Aug. 10, 2005).

 The row sums (of which 26618 is a member and where \(f\)=6) are as follows:

0, 7, 20, 46, 98, 202, 410, 826, 1658, 3322, 6650, 13306, 26618, 53242, 106490, 212986, 425978, 851962, 1703930, 3407866, 6815738, 13631482, 27262970, 54525946, 109051898, 218103802, 436207610, 872415226, 1744830458, 3489660922

Of course there are as many sequences as there are different values of \(f\) but none is listed in the OEIS apart from A100206 where \(f\)=6. In all sequences, the ratio of successive terms rapidly approaches 2.

The Perrin Sequence

Many years ago, in the bookstore at the bottom of SOGO in Pondok Indah Mall (Jakarta), I acquired a book by David Wells titled Prime Numbers: The Most Mysterious Figures in Math. I still have the physical copy but I also now have an electronic copy. On page 103, there is the information shown in Figure 1:

Figure 1

It so happens that the number representing my diurnal age today, 26149, is a member of this "very generalized Fibonacci sequence" and is in fact OEIS A050443:

A050443

a(0)=4, a(1)=0, a(2)=0, a(3)=3; thereafter a(n) = a(n-3) + a(n-4).

4, 0, 0, 3, 4, 0, 3, 7, 4, 3, 10, 11, 7, 13, 21, 18, 20, 34, 39, 38, 54, 73, 77, 92, 127, 150, 169, 219, 277, 319, 388, 496, 596, 707, 884, 1092, 1303, 1591, 1976, 2395, 2894, 3567, 4371, 5289, 6461, 7938, 9660, 11750, 14399, 17598, 21410, 26149

I was alerted to this connection to the book thanks to an OEIS reference that also remarks that the sequence is related to the Perrin sequence that also has the property that a(\(p\)) is divisible by \(p\) for primes \(p\). So what is the Perrin sequence? WolframMathWorld defines it as:$$P(n)=P(n-2)+P(n-3) \text{ where }P(0)=3,P(1)=0,P(2)=2$$Unusually, the Wolfram article also displays a cartoon (see Figure 2):

Figure 2: The above cartoon (Amend 2005) shows an unconventional sports
application of the Perrin sequence (right panel).
(The left two panels instead apply the Fibonacci numbers).

\(P(n)\) is also the solution of a third-order linear homogeneous recurrence equation having characteristic equation \(x^3-x-1=0\). The solutions to this equation are given by:$$\begin{align} x& = -\frac{1}{2} \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} + \frac{1}{2}\right)}^{\frac{1}{3}} {\left(i \, \sqrt{3} + 1\right)} - \frac{-i \, \sqrt{3} + 1}{6 \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} + \frac{1}{2}\right)}^{\frac{1}{3}}}\\x &= -\frac{1}{2} \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} + \frac{1}{2}\right)}^{\frac{1}{3}} {\left(-i \, \sqrt{3} + 1\right)} - \frac{i \, \sqrt{3} + 1}{6 \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} + \frac{1}{2}\right)}^{\frac{1}{3}}}\\ x &= {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} + \frac{1}{2}\right)}^{\frac{1}{3}} + \frac{1}{3 \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} + \frac{1}{2}\right)}^{\frac{1}{3}}}\end{align} $$The third and only real-valued solution above is the so-called plastic constant \( \approx 1.32471795... \), also called the:

• le nombre radiant
• minimal Pisot number
• plastic number
• plastic ratio
• platin number
• Siegel's number
• silver number
• silver constant 

It is the limiting ratio of the successive terms of the Padovan sequence or Perrin sequence. Thus we have:$$\lim_{n \to \infty} \frac{P(n)}{P(n-1)}=P \approx 1.32471795$$The Padovan sequence mentioned is similar to the Perrin except that it has different starting values:$$P(n)=P(n-2)+P(n-3) \text{ where }P(0)=0,P(1)=1,P(2)=1$$It should be noted that for OEIS A050443, the ratio of successive terms does not approach the plastic constant but instead 1.22074... which as far as I can determine doesn't have a particular name.

Figure 3

It was only after composing this post that I realised I had already made a post about the plastic number on Friday, 5th June 2020. This is well worth the read because it illustrates some applications of the number (as shown in Figure 3). The Greek letter \( \rho \) can be used to represent the plastic ratio. In which case, to quote from the earlier post and referencing Figure 3:

There are precisely three ways of partitioning a square into three similar rectangles:

• The trivial solution given by three congruent rectangles with aspect ratio 3:1.  

• The solution in which two of the three rectangles are congruent with the third one of twice the linear dimension of the congruent pair and where the rectangles have aspect ratio 3:2.  

• The solution in which the three rectangles are mutually non-congruent (all of different sizes) and where they have aspect ratio \( \rho^2 \). 

The ratios of the linear sizes of the three rectangles are: 

• \( \rho \) (large : medium) 

• \( \rho^2\)(medium : small) 

• \( \rho^3 \) (large : small). 

The internal, long edge of the largest rectangle (the square's fault line) divides two of the square's four edges into two segments each that stand to one another in the ratio ρ. The internal, coincident short edge of the medium rectangle and long edge of the small rectangle divides one of the square's other, two edges into two segments that stand to one another in the ratio \(\rho^4\).

Figure 4 shows the approximate measurements for a unit square in which the three rectangles are mutually non-congruent. We have:$$ \frac{b}{1-b}=\rho$$

Figure 4

Prouhet-Thue-Morse Sequence

I was reminded of this sequence when I rewatched a Numberphile YouTube video that related the sequence to the game of chess.

The Prouhet-Thue-Morse is a simple enough sequence but one with many practical applications. It can be described using formal mathematical notation but it can be described in so-called layman's terms as well. This gif from Wikipedia is an example of the latter:

A close look at this gif and it's clear enough how the sequence is being constructed. My last two posts have focussed on recurrence relations and the Prouhet-Thue-Morse sequence can be described more formally as a recurrence relation:$$ \begin{align} t_0 &= 0\\ t_{2n} &= t_n\\ t_{2n+1} &= 1 - t_n \end{align}$$wikiHow has a variety of algorithms for creating the sequence. One uses the recurrence relation as shown in Figure 1:

Figure 1

I incorporated this approach into SageMathCell as shown in Figure 2 (permalink):

Figure 2: permalink

Another approach, what wikiHow calls the Direct Definition, uses the binary form of the natural (decimal) numbers, calculates their binary sum and then uses the modulus 2 of this sum as the output. What's happening is that decimal numbers with an even number of 1's in their binary form are assigned a ZERO and those with an odd number of 1's are assigned a ONE.

\(t_0 = 0 \text{ and } t_n \equiv s_n \bmod{2} \text{ where }s_n \text{ is the binary sum of }n\)

This algorithm is even easier to implement in SageMathCell. See Figure 3 where the output is shown, for variety, as a string rather than a list of elements (permalink):

Figure 2: permalink

The following is an excellent video that I came across from a mathematician who, unconsciously, used the Thue-Morse sequence (sometimes the Prouhet part of the name is omitted) as a child to cope with his obsessive compulsive disorder. Later he describes how he unwittingly used the sequence to solve the Mathematics problem described in Figure 3:

Figure 3

Of course the sequence can be represented with elements other than 0's and 1's. For example, suppose that two persons want to divide an even number of items of equal value between themselves. If the choosing sequence goes ABABABAB ... or BABABABA ... then the person choosing second will always be behind 50% of the time in terms of what they've accumulated. However, using the Thus-Morse sequence, the lead will alternate and in fact represents the fairest way to share things:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABB

Finally, here is a video on the sequence that Stand-up Maths did some years ago: