Problem 1611

### Part (a)
1. Lemma 1: Let $n$ be a positive integer. Let $x_1, \ldots, x_n$ be pairwise distinct nonnegative real numbers and let $y_1, \ldots, y_n$ be real numbers. Then there exists a nonconstant *even* polynomial $f(x) \in \mathbb{R}[x]$ such that $f(x_i) = y_i$ for all $i \in \{1, 2, \ldots, n\}$.

Proof: Since $x_1, \ldots, x_n$ are nonnegative and pairwise distinct, then so are $x_1^2, \ldots, x_n^2$. By Lagrange's interpolation formula, there exists a polynomial $g(x) \in \mathbb{R}[x]$ such that $g(x_i^2) = y_i$ for every $i \in \{1, 2, \ldots, n\}$. Replacing $g(x)$ by $g(x) + \prod_{i=1}^n (x - x_i^2)$ if necessary, we can assume $g(x)$ is nonconstant. Now choose $f(x) = g(x^2)$.

2. Lemma 2: There exists a sequence of even polynomials $\{f_n(x)\}_{n \in \mathbb{Z}_{\ge 0}}$ such that:
- $f_n(x)$ is the zero polynomial if and only if $n = 0$, and
- for every nonnegative integers $n, k$ we have $f_n(k) = f_{|n-k|}(k)$.

Proof: We define $f_0(x), f_1(x), \ldots$ inductively, in this order. Initially define $f_0(x) \equiv 0$. Now, let $n$ be a positive integer and assume $f_0(x), \ldots, f_{n-1}(x)$ have been defined. By Lemma 1, there exists a nonconstant even polynomial $f_n(x) \in \mathbb{R}[x]$ such that $f_n(k) = f_{|n-k|}(k)$ whenever $k \in \mathbb{Z}$ and $1 \le k \le 2n-1$. Note that whenever $1 \le k \le 2n-1$ then $0 \le |n-k| \le n-1$, so the definition is well-defined. It remains to prove that $f_n(k) = f_{|n-k|}(k)$ for all nonnegative integers $n, k$. We divide into cases.

- Case 1: $k = 0$ or $k = 2n$. In those cases $|n-k| = n$ so the equation $f_n(k) = f_{|n-k|}(k)$ is tautological.
- Case 2: $1 \le k \le 2n-1$. The inequality $1 \le 2n-1$ implies that $n \ge 1$, so we are done by construction.
- Case 3: $k \ge 2n+1$. In this case $1 \le k \le 2(k-n)-1$, so
$$f_{|n-k|}(k) = f_{k-n}(k) = f_{|(k-n)-k|}(k) = f_n(k).$$

Since we have exhausted all cases, this proves the lemma.

3. Now choose even polynomials $\{f_n(x)\}_{n \in \mathbb{Z}_{\ge 0}}$ in $\mathbb{R}[x]$ which satisfy the conditions of Lemma 2. We now extend the sequence $\{f_n(x)\}_{n \in \mathbb{Z}_{\ge 0}}$ to $\mathbb{Z}$ by defining $f_n(x) = f_{-n}(x)$ whenever $n \in \mathbb{Z}$ and $n < 0$. Now since $f_0(x) \equiv 0$ and $f_1(x) \not\equiv 0$, then not all $f_n$ are equal. It remains to prove that $f_n(k) = f_{n+k}(k)$ for all integers $n, k$. Since $f_n(x) = f_{-n}(x)$ and $\{f_n(x)\}$ are all even polynomials, changing signs to both $n, k$ does not change the equation. Hence it is enough to assume that $n \ge 0$. We now split into cases.

- Case 1: $k \ge 0$. Then
$$f_{n+k}(k) = f_{|(n+k)-k|}(k) = f_n(k).$$
- Case 2: $k < 0$. Let $a = -k$. Then $a, n \ge 0$ so
$$f_n(k) = f_n(-a) = f_n(a) = f_{|n-a|}(a) = f_{|n+k|}(-k) = f_{n+k}(k).$$

This ends our proof.

The final answer is True