It’s been literally a year and half since our last post, but we still live. The blog still lives. 10,000 years etc etc.

Let’s get down to business. This problem has been on the queue for a year as well, and it’s time we finally put it on the books.

Q:

Let \(F_m\) be the \(m\)th Fibonacci number, defined by \(F_1 = F_2 = 1\) and for all \(m \geq 3\) \[ F_m = F_{m−1} + F_{m−2} \]

Let \(p(x)\) be the polynomial of degree \(1008\) such that \[ p(2n + 1) = F_{2n+1} \]

for \(n = 0,1,2,...,1008\).

Find integers \(j\) and \(k\) such that \(p(2019) = F_j − F_k\).

A:

We’re going to tackle this problem by first taking a small diversion into the land of polynomials. Specifically, we’ll be exploring a fact about polynomials that I learned in middle school. At the time, my math teacher had us play the following the game with quadratics:

Consider a quadratic polynomial, say, \(p(x) = 2x^2 + 5x - 7\). We construct the difference table of \(p(x)\) as follows:

The first row is just the values of \(p(0), p(1), p(2), p(3), p(4), p(5), p(6), ...\) i.e. \[ -7, 0, 11, 26, 45, 68, 95, … \]

The second row consists of the differences between adjacent values in the first row: \[ 0 - -7 = 7, 11-0 = 11, 26-11 = 15, 45-26 = 19, 68-45 = 23, 95-68 = 27, … \]

The third row consists of the differences between adjacent values in the second row: \[ 11-7 = 4, 15-11 = 4, 19-15 = 4, 23-19 = 4, 27-23 = 4, … \]

The full table is thus as follows (for clarity of visualization): \[ -7, 0, 11, 26, 45, 68, 95, … \] \[ 7, 11, 15, 19, 23, 27, … \] \[ 4, 4, 4, 4, 4, … \]

If you play around with different polynomials, you’ll find that the same result always seems to hold: the third row is always constant!

In fact, this can be extended to polynomials in general: If \(p(x)\) is a degree \(n\) polynomial, then the \(n+1\)th row of \(p(x)\)’s difference table is constant.

Additionally, we note that in our original table construction we generated the first row by starting at \(x=0\), and then we increased \(x\) in increments of \(1\). The fact that the \(n+1\)th row is constant holds for any initial value, and any constant increment.

Let’s quickly prove this fact.

Lemma 1

Let \(p(x)\) be a polynomial of degree \(n\). For any constant \(\delta\), we define the recursive sequence of functions \(\{ d_i \}\) as follows:

\[ d_0(x) = p(x) \] \[ d_{i+1}(x) = d_i(x+\delta) - d_i(x) \]

Then \(d_n(x)\) is a constant function.

Proof Lemma 1

Let’s call \(\{ d_i \}\) the sequence of difference functions for \(p(x)\). We call \(d_i\) the \(i\)th difference function of \(p(x)\).

To prove the lemma, we will use induction.

For the base case, we observe that if \(n=0\), then \(d_n(x) = d_0(x) = p(x)\) which is constant, since the degree of \(p(x)\) is 0.

For the inductive step, assume that the lemma holds for all \(k \leq n\). Let \(p(x)\) be a polynomial of degree \(n+1\).

We first note that \[ d_1(x) = p(x+\delta) - p(x) \] is a polynomial with degree at most \(n\). This can be easily seen by noting that \(p(x+\delta)\) is also a degree \(n+1\) polynomial with the same leading term as \(p(x)\). Thus \(p(x+\delta) - p(x)\) is also a polynomial. In this difference, the leading terms will cancel, meaning the highest degree term is at most \(n\).

By the recursive definition of \(\{ d_i \}\), we observe that \(d_{n+1}\) is in fact the \(n\)th difference function for the polynomial \(d_1\). The inductive hypothesis implies that \(d_{n+1}\) is thus constant. This completes the induction.

Corollary of Lemma 1

Let \(p(x)\) be a degree \(n\) polynomial.

The fact that the \(n+1\)th row of the difference table of \(p(x)\) is constant is a direct corollary of Lemma 1. Let \(\delta = 1\) and \(\{ d_i \}\) be the sequence of difference functions for \(p(x)\). We observe that the first row of the difference table is equal to \[ d_0(0), d_0(1), d_0(2), … \]

The second row is \[ d_1(0), d_1(1), d_1(2), … \]

And in general, the \(k+1\)th row is \[ d_k(0), d_k(1), d_k(2), … \]

It follows immediately that the \(n+1\)th row is \[ d_n(0), d_n(1), d_n(2), … \]

which by Lemma 1 implies that the \(n+1\)th row is in fact constant.

Back to the Problem

To restate the problem, \(p(x)\) is a degree 1008 polynomial such that for \(x = 1, 3, 5, 7, ..., 2017\) \[ p(x) = F_x \]

and we are trying to find the value of \(p(2019)\).

Let’s construct the difference table for \(p(x)\) with increment \(\delta = 2\).

The first row is \[ F_1, F_3, F_5, F_7, F_9, …, F_{2017}, p(2019), … \]

To compute the subsequent rows, we note the very useful fact that for any \(k\), we have \(F_{k+2} - F_k = F_{k+1}\). Thus the second row is \[ F_2, F_4, F_6, F_8, …, F_{2016}, p(2019) - F_{2017}, … \]

The third row is \[ F_3, F_5, F_7, …, F_{2015}, p(2019) - F_{2017} - F_{2016}, … \]

The fourth row is \[ F_4, F_6, F_8, …, F_{2014}, p(2019) - F_{2017} - F_{2016} - F_{2015}, … \]

Continuing this construction, it is easy to show that the \(1009\)th row is \[ F_{1009}, p(2019) - \sum_{k=1010}^{2017}{F_k}, … \]

By our proven fact above, since \(p(x)\) is of degree \(1008\), the \(1009\)th row of its difference table must be constant. This implies that \[ F_{1009} = p(2019) - \sum_{k=1010}^{2017}{F_k} \]

Or, after rearranging: \[ p(2019) = \sum_{k=1009}^{2017}{F_k} \]

There are a plethora of methods for simplifying this sum of consecutive Fibonacci numbers. I will share what I find to be the nicest looking one. Adding \(F_{1010}\) to both sides of the equation, we have \[ p(2019) + F_{1010} = F_{1010} + F_{1009} + F_{1010} + F_{1011} + F_{1012} + … + F_{2017} \] \[ = F_{1011} + F_{1010} + F_{1011} + F_{1012} + … + F_{2017} \] \[ = F_{1012} + F_{1011} + F_{1012} + … + F_{2017} \] \[ = F_{1013} + F_{1012} + … + F_{2017} \] \[ … \] \[ = F_{2018} + F_{2017} \] \[ = F_{2019} \]

(For each step, I am just combining the first two terms on the RHS)

This ultimately gives us \[ p(2019) = F_{2019} - F_{1010} \]