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

Vieta Jumping

I noticed this problem in a YouTube video and I thought I'd test out Gemini's ability to solve it. I posed this question:

Let's say that a and b are positive integers such a*b + 1 divides a^2+b^2 to give an integer m. Prove that m must be a perfect square.

Here was the response with impeccable LaTeX formatting:

This is a famous problem from the 1988 International Mathematical Olympiad (IMO), often referred to as the "Vieta Jumping" problem. It is considered one of the most beautiful problems in Olympiad history.

Here is the proof using the method of Infinite Descent (specifically, Vieta Jumping).

1. Setup the Equation

Let the given expression equal an integer $m$. We are given that $a$ and $b$ are positive integers and:

$$\frac{a^2 + b^2}{ab + 1} = m$$

We can rewrite this equation as:

$$a^2 - m(ab) - m + b^2 = 0$$

$$a^2 - m(ab) + b^2 - m = 0$$

We want to prove that $m$ is a perfect square.

2. Assumption for Contradiction

Assume, for the sake of contradiction, that $m$ is not a perfect square.

Let $S$ be the set of all pairs of positive integers $(a, b)$ that satisfy the equation for this specific non-square $m$:

$$S = \{ (a, b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \mid \frac{a^2 + b^2}{ab + 1} = m \}$$

Since we assumed solutions exist (the problem states $a, b$ are positive integers), the set $S$ is not empty.

3. Infinite Descent (Minimality)

Among all pairs in $S$, let us choose the pair $(A, B)$ that minimizes the sum $A + B$. Without loss of generality, assume $A \ge B$.

Since $(A, B)$ is a solution, it satisfies the quadratic equation in terms of $A$:

$$A^2 - (mB)A + (B^2 - m) = 0$$

Let’s treat this as a quadratic equation in $x$:

$$x^2 - (mB)x + (B^2 - m) = 0$$

We know one root is $x_1 = A$. By Vieta's formulas, since it is a quadratic, there must be a second root, $x_2$. The properties of the roots are:

1. Sum of roots: $x_1 + x_2 = mB \implies x_2 = mB - A$

2. Product of roots: $x_1 x_2 = B^2 - m \implies x_2 = \dfrac{B^2 - m}{A}$

4. Analyzing the Second Root ($x_2$)

We need to determine the nature of $x_2$.

• Is $x_2$ an integer?

  Yes. From the sum of roots ($x_2 = mB - A$), since $m, B, A$ are integers, $x_2$ is an integer.

• Is $x_2$ equal to zero?

  If $x_2 = 0$, then the product of roots $x_1 x_2 = 0$.

  This implies $B^2 - m = 0$, or $m = B^2$.

  This would mean $m$ is a perfect square. However, we assumed at the start that $m$ is not a perfect square. Therefore, $x_2 \neq 0$.

• Is $x_2$ negative?

  Consider the quadratic equation: $x^2 - mBx + B^2 - m = 0$.

  If $x_2 < 0$, let's check the value of the expression for negative $x$.

  $$x_2^2 - mB(x_2) + B^2 - m$$

  Since $x_2$ is a negative integer (e.g., $-1, -2...$) and $m, B \ge 1$:

  • $x_2^2 > 0$

  • $-mBx_2 > 0$ (negative times negative is positive)

  • $B^2 - m$?

    Actually, we can check this simpler: From the product of roots, $x_1 x_2 = B^2 - m$.

    Since $x_1 = A > 0$, if $x_2 < 0$, then $B^2 - m < 0$, so $m > B^2$.

    However, looking at the sum of roots: $x_2 = mB - A$.

    If $x_2 < 0$, then $mB < A$. Thus $A > mB > B^2 \cdot B = B^3$.

    However, checking the value of the polynomial $f(x) = x^2 - mBx + B^2 - m$:

    If $x_2 \le -1$, then $f(x_2) \ge 1 + mB + B^2 - m = 1 + B^2 + m(B-1)$.

    Since $B \ge 1$ and $m \ge 1$, $f(x_2) \ge 1 + 1 + 0 > 0$.

    This contradicts $f(x_2) = 0$. Therefore, $x_2$ cannot be negative.

Conclusion: $x_2$ must be a positive integer.

5. Contradiction

Since $x_2$ is a positive integer, the pair $(x_2, B)$ is also a solution in the set $S$ (because the equation is symmetric with respect to $a$ and $b$, and substituting $x_2$ into the quadratic yields 0).

Now, let's look at the size of $x_2$. From the product of roots:

$$x_2 = \frac{B^2 - m}{A}$$

Since $m$ is a positive integer (and we assumed not a square, so usually $m > 1$ unless trivial), we have $B^2 - m < B^2$.

Therefore:

$$x_2 < \frac{B^2}{A}$$

Recall we assumed $A \ge B$. Thus:

$$x_2 < \frac{B^2}{B} = B \le A$$

So, $x_2 < A$.

This creates a new solution $(x_2, B)$ where the sum of the components is $x_2 + B$.

Since $x_2 < A$, it follows that:

$$x_2 + B < A + B$$

This contradicts our initial statement that $(A, B)$ was the solution with the minimal sum.

6. Final Result

The only way to avoid this contradiction is if the case "$x_2$ is a positive integer" never happens.

As shown in step 4, the only alternative is $x_2 = 0$.

If $x_2 = 0$, then $m = B^2$.

Therefore, $m$ must be a perfect square.

I then asked: Where does the terms "Vieta" and "Vieta Jumping" come from?

The terms come from two distinct places: a 16th-century French mathematician and a legendary problem from the 1988 International Mathematical Olympiad.

1. "Vieta" comes from François Viète

The term "Vieta" refers to François Viète (1540–1603), often known by his Latinized name Franciscus Vieta.

• Who he was: A French mathematician who is arguably the "father of modern algebra." He was the first to systematically use letters to represent numerical unknowns (like $x$ and $y$) and parameters (like $a$ and $b$) in equations.

• The Connection: He is most famous for Vieta's Formulas, which connect the roots of a polynomial to its coefficients.

  • For a quadratic $ax^2 + bx + c = 0$ with roots $r_1$ and $r_2$, the formulas are:

    $$r_1 + r_2 = -\frac{b}{a}$$
    $$r_1 \cdot r_2 = \frac{c}{a}$$

  • This specific relationship (sum and product of roots) is the mechanical "engine" that makes the Vieta Jumping proof work.

2. "Vieta Jumping" comes from IMO 1988

The term "Vieta Jumping" (also called Root Flipping) is a relatively modern colloquialism invented by the math competition community. It was coined to describe the specific technique used to solve Problem 6 of the 1988 International Mathematical Olympiad (IMO).

The Legend of Problem 6

The problem you just saw ($ab+1 \mid a^2+b^2$) is legendary in the history of mathematics competitions.

• The Difficulty: When the problem was submitted to the IMO jury in 1988 (held in Australia), the problem selection committee—which included famous number theorists—could not solve it within the allotted 6 hours. They actually considered rejecting it because they thought it was too hard for high school students.

• The Surprise: Despite the judges' struggle, 11 students found the correct solution during the actual competition.

• The Technique: The students solved it using the method of Infinite Descent combined with Vieta's Formulas.

  • They viewed the expression as a quadratic equation.

  • They used Vieta's formulas to "swap" (or jump) one root for another smaller root
    ($x_2 = mB - A$).

  • This "jump" creates a smaller integer solution, eventually leading to a contradiction.

Because this specific "root swapping" move was the key to cracking the hardest problem in IMO history, the community began calling the technique "Vieta Jumping."

---

Summary Table

Term	Origin
Vieta	Latin name of François Viète (1540–1603), the creator of the root formulas.
Vieta Jumping	A nickname given to the descent method popularized by the solution to IMO 1988 Problem 6.

Would you like me to show you another famous problem that can be solved using this technique?

The Vieta Jumping Trick That Solves an Impossible Olympiad Problem

This video provides a visual walkthrough of the exact technique discussed, breaking down the 1988 IMO problem step-by-step.