United States — Team Selection Test

Let
$$X_n = \sum_{i=0}^{n} (-1)^i \binom{n}{i} x_i \quad \text{and} \quad Y_n = \sum_{i=0}^{n} (-1)^i \binom{n}{i} y_i.$$
For nonnegative integers $i \le j$, consider the expression
$$\sum_{k=i}^{j} (-1)^k \binom{k}{i} \binom{j}{k}.$$
Viewing $\binom{j}{k}$ as the number of ways to choose a $k$-element subset of a $j$-element set and $\binom{k}{i}$ as the number of ways to choose an $i$-element subset which is contained in this chosen $k$-element set, the principle of inclusion-exclusion shows that $(-1)^j$ times this sum is the number of ways to choose an $i$-element subset from a $j$-element set that coincides with the set itself. Thus, the sum is $(-1)^i$ if $i = j$ and $0$ otherwise. Therefore, we may write
$$\begin{aligned} \sum_{r=0}^{n} (-1)^r \binom{n}{r} x_r y_r &= \sum_{i=0}^{n} \sum_{j=0}^{n} (-1)^{i+j} x_i y_j \sum_{r=0}^{n} (-1)^r \binom{n}{r} \left[ \sum_{k=i}^{r} (-1)^k \binom{k}{i} \binom{r}{k} \right] \left[ \sum_{\ell=j}^{r} (-1)^\ell \binom{\ell}{j} \binom{r}{\ell} \right] \\ &= \sum_{k=0}^{n} \sum_{\ell=0}^{n} \left[ \sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} x_i \right] \left[ \sum_{j=0}^{\ell} (-1)^{\ell-j} \binom{\ell}{j} y_j \right] \left[ \sum_{r=0}^{n} (-1)^r \binom{n}{r} \binom{r}{k} \binom{r}{\ell} \right] \\ &= \sum_{k=0}^{n} \sum_{\ell=0}^{n} (-1)^{n+k+\ell} X_k Y_\ell \left[ \sum_{r=0}^{n} (-1)^{n-r} \binom{n}{r} \binom{r}{k} \binom{r}{\ell} \right]. \end{aligned}$$
Again by the principle of inclusion-exclusion, the final expression in brackets counts the number of ways to choose a $k$-element subset and an $\ell$-element subset of an $n$-element set whose union is the entire set (again by the principle of inclusion-exclusion), so it is $0$ if $k + \ell < n$.

Now, let $e$ be arbitrary, let $N$ be so large that $p^e$ divides both $X_m$ and $Y_m$ whenever $m \ge N/2$ (such an $N$ exists by the definition of $p$-pod), and take $n \ge N$. Then, whenever $k + \ell \ge n \ge N$, at least one of $k$ or $\ell$ is at least $N/2$, so $p^e$ will divide either $X_k$ or $Y_\ell$. We conclude that $p^e$ divides every term in the sum, and that therefore for each $n \ge N$, $p^e$ divides
$$\sum_{r=0}^{n} (-1)^r \binom{n}{r} x_r y_r,$$
hence $\{x_n y_n\}_{n=0}^\infty$ is a $p$-pod.

Solution 2:

For a sequence $\{z_n\}_{n=0}^\infty$ and an integer $m \ge 0$, define
$$\Delta^m z_n = \sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} z_{n+k},$$
so that $\{\Delta^m z_n\}_{n=0}^\infty$ is the sequence of $m$-fold finite differences in $\{z_n\}$. With this notation, $\{z_n\}$ is a $p$-pod if and only if for every $e > 0$ there is an $N \ge 0$ such that whenever $m \ge N$, $p^e \mid \Delta^m z_0$.

Lemma 1. The sequence $\{z_n\}$ is a $p$-pod if and only if for every $e > 0$ there is an $N \ge 0$ such that whenever $m \ge N$, $p^e$ divides $\Delta^m z_n$ for every $n \ge 0$.

Proof. Indeed, recall (or verify) that for any $m, n \ge 0$, we have
$$\Delta^{m+1} z_n = \Delta^m z_{n+1} - \Delta^m z_n, \quad \text{or} \quad \Delta^m z_{n+1} = \Delta^m z_n + \Delta^{m+1} z_n. \qquad (33)$$
A trivial induction using (33) shows that the same $N$ as in the definition of $p$-pod works for all $n \ge 0$. $\square$

Now, let $\{x_n\}$ and $\{y_n\}$ be $p$-pods. By Lemma 1, there exists an $N$ such that for all $n$, $\Delta^m x_n \equiv 0 \pmod{p^e}$ for $m \ge N$. Let $f(t)$ be the monic degree $N$ polynomial with rational coefficients such that $f(n) = x_n$ for $n = 0, 1, \dots, N$. By definition, we see that $\Delta^m x_0 = \Delta^m f(0)$ for $m \le N$; further, because $\Delta^m f(n) = 0$ for $m \ge N$, we see that $\Delta^m x_0 \equiv \Delta^m f(0) \pmod{p^e}$ for all $m \ge 0$. An easy induction using (33) then shows that $\Delta^m x_n \equiv \Delta^m f(n) \pmod{p^e}$ for all $m, n \ge 0$. Taking $m = 0$ in particular gives that $f(n) \equiv x_n \pmod{p^e}$ for all $n \ge 0$. Similarly, we find a polynomial $g(t)$ such that $g(n) \equiv y_n \pmod{p^e}$ for all $n \ge 0$.

But then $h(t) = f(t)g(t)$ has the property that $h(n) \equiv x_n y_n \pmod{p^e}$ for all $n \ge 0$. Therefore, if $h(t)$ has degree $M$, then for any $m \ge M$ and $n \ge 0$ we have
$$\Delta^m \{x_n y_n\} \equiv \Delta^m h(n) \equiv 0 \pmod{p^e},$$
and we are done by Lemma 1.