Eighth IMAR MATHEMATICAL COMPETITION, 2010

A polynomial $P$ of degree at most $k$ with complex coefficients is integer-valued if and only if
$$P = \sum_{j=0}^{k} a_j \binom{X}{j} = \sum_{j=0}^{k} \frac{a_j}{j!} X(X-1) \cdots (X-j+1),$$
where the $a_j$ are all integer numbers, so its coefficients are rational.

We show that for such a $P$, the sequence $((-1)^{P(n)})_{n \in \mathbb{N}}$ is periodic with period $2^r$, where $r = \min\{s : 2^s > k\}$. To this end, it suffices to show that if $j < 2^s$ and $m$ is integer, then $\binom{m}{j} \equiv \binom{m+2^s}{j} \mod 2$. These are the coefficients of $X^j$ in the expansions of $(1+X)^m$ and $(1+X)^{m+2^s}$, respectively. The congruence $(1+X)^{2^s} \equiv 1+X^{2^s} \mod 2$ follows easily by induction on $s$. Hence $(1+X)^{m+2^s} = (1+X)^m (1+X^{2^s}) \mod 2$. Since $j$ is less than $2^s$, it is immediate that the coefficients of $X^j$ in $(1+X)^m$ and $(1+X)^{m+2^s}$ have the same parity.

Conversely, let $\alpha_0, \dots, \alpha_{2^r-1}$ be arbitrary integers, and let $\beta_0, \dots, \beta_{2^r-1}$ be the solution to the lower triangular system of linear equations
$$\sum_{i=0}^{2^r-1} \beta_i \binom{j}{i} = \alpha_j, \quad j = 0, \dots, 2^r-1.$$
Then
$$\sum_{i=0}^{2^r-1} \beta_i \binom{X}{i} = \sum_{i=0}^{2^r-1} \frac{\beta_i}{i!} X(X-1)\cdots(X-i+1)$$
realizes the sequence $(-1)^{\alpha_j}$, $j = 0, \dots, 2^r - 1$, and its extension with period $2^r$.

Given an integer-valued polynomial $P$ with rational coefficients, we show that the sequence $((-1)^{P(n)})_{n \in \mathbb{N}}$ is periodic with period a power of $2$. Clearly, it is sufficient to show that, for some non-negative integer $s$, the integer numbers $P(n)$ and $P(n + 2^s)$ both have the same parity, whatever $n \in \mathbb{N}$. To this end, consider a positive integer $m$ such that $Q = mP$ is a polynomial with integral coefficients (e.g., let $m$ be the least common multiple of the denominators of the coefficients of $P$ when written in lowest terms), let $2^r$ be the highest power of $2$ dividing $m$, and let $s$ be an integer greater than $r$. Write $m = 2^r(2m' + 1)$ and fix a positive integer $n$. Since $2^s$ divides the difference
$$Q(n + 2^s) - Q(n) = m(P(n + 2^s) - P(n)) = 2^r(2m' + 1)(P(n + 2^s) - P(n))$$
and $s > r$, the conclusion follows.

Conversely, given a sequence $(\varepsilon_n)_{n \in \mathbb{N}}$ of plus and minus ones which is periodic with period $2^r$, let
$$a_k = \begin{cases} 0, & \text{if } \varepsilon_k = 1, \\ 1, & \text{if } \varepsilon_k = -1, \end{cases} \quad k = 0, \dots, 2^r - 1,$$
and consider the polynomial (Lagrange)
$$\begin{align*} P &= \sum_{k=0}^{2^r-1} a_k \prod_{j \neq k} \frac{X-j}{k-j} \\ &= \sum_{k=0}^{2^r-1} (-1)^{k+1} a_k \left( \frac{1}{k!} \prod_{0 \le j < k} (X-j) \right) \left( \frac{1}{(2^r-k-1)!} \prod_{k<j \le 2^r-1} (X-j) \right) \\ &= \sum_{k=0}^{2^r-1} (-1)^{k+1} a_k \binom{X}{k} \binom{X-k-1}{2^r-k-1}. \end{align*}$$

Clearly, $P$ has rational coefficients, is integer-valued, and $P(k) = a_k$, $k = 0, \dots, 2^r - 1$, so $\varepsilon_k = (-1)^{P(k)}$, $k = 0, \dots, 2^r - 1$. To prove that the latter extends to all of $\mathbb{N}$, it is sufficient to show that $P(n)$ and $P(n + 2^r)$ both have the same parity, whatever $n \in \mathbb{N}$. This amounts to showing that if $j, m \in \mathbb{N}$ and $j < 2^r$, then $\binom{m}{j}$ and $\binom{m+2^r}{j}$ have the same parity. Recalling that $\binom{2^r}{i}$, $i = 1, \dots, 2^r - 1$, are all even, this follows for instance from the identity
$$\binom{m+2^r}{j} = \sum_{i=0}^{j} \binom{m-i}{j-i} \binom{2^r}{i};$$
or, which is actually the same, from the argument in Solution 1.