Putnam 2019, Problem B-5

Let \(F_m\) be the \(m\)th Fibonacci number, defined by \(F_1 = F_2 = 1\) and \(F_m = F_{m-1} + F_{m-2}\) for all \(m \geq 3\). Let \(p(x)\) be the polynomial of degree \(1008\) such that \(p(2n+1) = F_{2n+1}\) for \(n = 0, 1, 2, \ldots, 1008\). Find integers \(j\) and \(k\) such that \(p(2019) = F_j - F_k\).

Solution:
**Solution 1.** We prove that $(j,k) = (2019,1010)$ is a valid solution. More generally, let $p(x)$ be the polynomial of degree $N$ such that $p(2n+1) = F_{2n+1}$ for $0 \leq n \leq N$. We will show that $p(2N+3) = F_{2N+3} - F_{N+2}$.

Define a sequence of polynomials $p_0(x), \ldots, p_N(x)$ by $p_0(x) = p(x)$ and $p_k(x) = p_{k-1}(x) - p_{k-1}(x+2)$ for $k \geq 1$. Then by induction on $k$, it is the case that $p_k(2n+1) = F_{2n+1+k}$ for $0 \leq n \leq N-k$, and also that $p_k$ has degree (at most) $N-k$ for $k \geq 1$. Thus $p_N(x) = F_{N+1}$ since $p_N(1) = F_{N+1}$ and $p_N$ is constant.

We now claim that for $0 \leq k \leq N$, $p_{N-k}(2k+3) = \sum_{j=0}^k F_{N+1+j}$. We prove this again by induction on $k$: for the induction step, we have
$$p_{N-k}(2k+3) = p_{N-k}(2k+1) + p_{N-k+1}(2k+1)$$
$$= F_{N+1+k} + \sum_{j=0}^{k-1} F_{N+1+j}.$$

Thus we have $p(2N+3) = p_0(2N+3) = \sum_{j=0}^N F_{N+1+j}$. Now one final induction shows that $\sum_{j=0}^m F_j = F_{m+2} - 1$, and so $p(2N+3) = F_{2N+3} - F_{N+2}$, as claimed. In the case $N = 1008$, we thus have $p(2019) = F_{2019} - F_{1010}$.

**Solution 2.** This solution uses the Lagrange interpolation formula: given $x_0, \ldots, x_n$ and $y_0, \ldots, y_n$, the unique polynomial $P$ of degree at most $n$ satisfying $P(x_i) = y_i$ for $i = 0, \ldots, n$ is
$$\sum_{i=0}^n P(x_i) \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}.$$

Write
$$F_n = \frac{1}{\sqrt{5}}(\alpha^n - \beta^n), \quad \alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}.$$

For $\gamma \in \mathbb{R}$, let $p_\gamma(x)$ be the unique polynomial of degree at most 1008 satisfying
$$p_1(2n+1) = \gamma^{2n+1}, p_2(2n+1) = \gamma^{2n+1} (n = 0, \ldots, 1008);$$
then $p(x) = \frac{1}{\sqrt{5}}(p_\alpha(x) - p_\beta(x))$.

By Lagrange interpolation,
$$p_\gamma(2019) = \sum_{n=0}^{1008} \gamma^{2n+1} \prod_{0 \leq j \leq 1008, j \neq n} \frac{2019 - (2j+1)}{(2n+1) - (2j+1)}$$
$$= \sum_{n=0}^{1008} \gamma^{2n+1} \prod_{0 \leq j \leq 1008, j \neq n} \frac{1009 - j}{n - j}$$
$$= \sum_{n=0}^{1008} \gamma^{2n+1} (-1)^{1008-n} \binom{1009}{n}$$
$$= -\gamma((\gamma^2 - 1)^{1009} - (\gamma^2)^{1009}).$$

For $\gamma \in \{\alpha,\beta\}$ we have $\gamma^2 = \gamma + 1$ and so
$$p_\gamma(2019) = \gamma^{2019} - \gamma^{1010}.$$

We thus deduce that $p(x) = F_{2019} - F_{1010}$ as claimed.

**Remark.** Karl Mahlburg suggests the following variant of this. As above, use Lagrange interpolation to write
$$p(2019) = \sum_{j=0}^{1008} \binom{1009}{j} F_j;$$
it will thus suffice to verify (by substituting $j \mapsto 1009-j$) that
$$\sum_{j=0}^{1009} \binom{1009}{j} F_{j+1} = F_{2019}.$$

This identity has the following combinatorial interpretation. Recall that $F_{n+1}$ counts the number of ways to tile a $1 \times n$ rectangle with $1 \times 1$ squares and $1 \times 2$ dominoes (see below). In any such tiling with $n = 2018$, let $j$ be the number of squares among the first 1009 tiles. These can be ordered in $\binom{1009}{j}$ ways, and the remaining $2018 - j - 2(1009 - j) = j$ squares can be tiled in $F_{j+1}$ ways.

As an aside, this interpretation of $F_{n+1}$ is the oldest known interpretation of the Fibonacci sequence, long predating Fibonacci himself. In ancient Sanskrit, syllables were classified as long or short, and a long syllable was considered to be twice as long as a short syllable; consequently, the number of syllable patterns of total length $n$ equals $F_{n+1}$.

**Remark.** It is not difficult to show that the solution $(j,k) = (2019,2010)$ is unique (in positive integers). First, note that to have $F_j - F_k > 0$, we must have $k < j$. If $j < 2019$, then
$$F_{2019} - F_{1010} = F_{2018} + F_{2017} - F_{1010} > F_j - F_k.$$

If $j > 2020$, then
$$F_j - F_k \geq F_j - F_{j-1} = F_{j-2} \geq F_{2019} > F_{2019} - F_{1010}.$$

Since $j = 2019$ obviously forces $k = 1010$, the only other possible solution would be with $j = 2020$. But then
$$(F_j - F_k) - (F_{2019} - F_{1010}) = (F_{2018} - F_k) + F_{1010}$$
which is negative for $k = 2019$ (it equals $F_{1010} - F_{2017}$) and positive for $k \leq 2018$.