= Solution
The <binomial polynomial> $P_r$ equals $1$ when $r=0$. For $n\geq0$, it has value $\binom nr$ if $r\leq n$ and value zero otherwise. These are <integers>. If $n=-k<0$, then
$$
P_r(-k)=(-1)^r\frac{k(k+1)\cdots(k+r-1)}{r!}
=(-1)^r\binom{k+r-1}{r}\in\mathbb Z.
$$
Hence each $P_r$ is an <integer-valued polynomial> on all of $\mathbb Z$, including negative arguments.
For $r\geq1$, factor the common product in the two <polynomials>:
$$
P_r(X)-P_r(X-1)
=\frac{(X-1)\cdots(X-r+1)}{r!}\bigl[X-(X-r)\bigr]
=P_{r-1}(X-1).
$$
For $r=1$ the common product is empty and equals $1$, so this argument also covers that boundary case.
The <polynomial> $P_r$ has <polynomial degree> $r$ and <leading coefficient> $1/r!$. For a <polynomial> $F$ of <polynomial degree> $d$ with <leading coefficient> $a_d\in\mathbb Q$, subtract $d!a_dP_d$; the remainder has smaller <polynomial degree>. Repeating gives the required expansion with <rational numbers> $c_r$. For uniqueness, suppose two expansions differ and let $s$ be the largest index with different coefficients. Their difference then has a nonzero term of <polynomial degree> $s$, with <leading coefficient> equal to that coefficient difference divided by $s!$. It cannot be the zero <polynomial>. Thus the expansion is unique.
Replacing $X$ by $X+1$ in the earlier identity gives $\Delta P_r(X)=P_{r-1}(X)$ for $r\geq1$, while $\Delta P_0=0$. By linearity of the <forward difference operator>,
$$
\boxed{\Delta F(X)=\sum_{r=0}^{d-1}c_{r+1}(F)P_r(X).}
$$
An empty sum is zero when $d=0$. If $H=F-G$ were nonconstant, with <polynomial degree> $s\geq1$ and <leading coefficient> $a_s$, then $\Delta H$ would have <polynomial degree> $s-1$ and <leading coefficient> $sa_s\ne0$. Therefore $\Delta F=\Delta G$ <forces> $H$ to be constant.
There is a direct way to recover every coefficient. Since $P_0(0)=1$ and $P_j(0)=0$ for $j\geq1$, repeated application of the <forward difference operator> gives
$$
\boxed{c_r(F)=\Delta^r F(0)=\sum_{j=0}^r(-1)^{r-j}\binom rj F(j).}
$$
The last equality follows by expanding $(T-I)^r$, where $TF(X)=F(X+1)$; the commuting shifts obey the <binomial theorem>. If $F$ is an <integer-valued polynomial>, every summand on the right is an <integer>, proving that all $c_r(F)$ are <integers>. Together with the first paragraph this gives both directions of the <Newton series for an integer-valued polynomial sequence> description.
Back to article page
