整数値多項式の意味と2つの必要十分条件

$k=0$ のときは $P(x)$ は定数関数なので定理1が成立。

$k=t$ のときに定理が成立すると仮定する。$t+1$ 次多項式 $P(x)$ に対して $P(n)$ から $P(n+t+2)$ までが整数とする。

このとき，階差 $Q(x)=P(x+1)-P(x)$ を考えると，

• $Q(n)$ から $Q(n+t+1)$ まで整数
• $Q(x)$ は $t$ 次多項式

よって帰納法の仮定より $Q(x)$ は整数値多項式。階差が整数なので $P(x)$ も整数値多項式。

補間点を $x_i=n+i\:(i=0,...,k)$ としてラグランジュ補間を使うと， $$P(x)=\displaystyle\sum_{i=0}^{k}P(x_i)\dfrac{f_i(x)}{f_i(x_i)}$$

ただし，$f_i(x)=\displaystyle\prod_{k\neq i}(x-x_k)$

$P(x_i)$ は整数なので $\dfrac{f_i(x)}{f_i(x_i)}$ が整数であることを示せば十分。これは以下のように計算すればわかる：

• 分母の絶対値は $|f_i(x_i)|=i!\times (k-i)!$
• $x$ が整数のとき，分子の絶対値 $f_i(x)$ は「$x-n$ から $x-n-i+1$ までの積」と「$x-n-i-1$ から $x-n-k$ までの積」の積。つまり「連続する $i$ 個の整数の積」と「連続する $k-i$ 個の整数の積」の積。つまり $i!\times (k-i)!$ の倍数である(※)。

$\Leftarrow$ はさきほど述べたように各 $c_t(x)$ が整数値多項式であることから従う。

$\Rightarrow$ を証明する。$x=0,1,...,k$ に対して$$P(x)=\displaystyle\sum_{t=0}^k a_tc_t(x)$$ を満たすような「実数」$a_0,...,a_k$ は以下のように求められる：

• 両辺に $x=0$ を代入すると右辺は $t=0$ の項以外が消えるので $a_0=P(0)$
• $x=1$ を代入すると $a_1=P(1)-a_0$
• $x=2$ を代入すると $a_2=P(2)-2a_1-a_0$
• 以下同様に $x=k$ まで順々に代入していくと $a_k$ まで求まる。

$k$ 次多項式は，$k+1$ 点で値が決まったら一意に定まるので結局任意の $x$ に対して $$P(x)=\displaystyle\sum_{t=0}^k a_tc_t(x)$$ となる。

そして，上記の求め方の各式は $a_t=P(t)-整数$ という形なので，$P(0),...,P(k)$ が整数なら $a_0,...,a_k$ も整数である。