次: 直接計算か漸化式か 上: 数学的帰納法か直接証明か 前: 有理数値関数［02京大後期理系改題］

整数値関数［08東工大理特］

問題     

$n$を自然数，$P(x)$を$n$次多項式とする． $P(0),\ P(1),\ \cdots,\ P(n)$が整数ならば， すべての整数$k$に対し，$P(k)$は整数であることを証明せよ．

方針

1.

次数についての数学的帰納法

2.

$f(x)$を具体的に書き表す直接法１． ${}_N\mathrm{C}_n$は$N$の$n$次式であるが，この$N$を$x$に置きかえた式を使う．

3.

$f(x)$を具体的に書き表す直接法２． ラグランジュの補間公式を用いる．

解法1

命題： $n$次多項式$P(x)$において， $x=0,\ 1,\ \cdots,\ n$に対して $P(0),\ P(1),\ \cdots,\ P(n)$が整数ならば， すべての整数$k$に対し$P(k)$は整数である．

が $n=0,\ 1,\ 2,\ \cdots$に対して成立することを，$n$に関する数学的帰納法で証明する．

$n=0$のとき．$P(x)=a$とおく．$P(0)=a$が整数なので， 任意の整数$k$に対して$P(k)=a$は整数である．

$1,\ 2,\ \cdots,\ n-1$に対して命題が成立するとし，$n$のときの成立を示す．

$P(x)=a_nx^n+[ n-1次以下の項のみ]$ とおく．

$$\begin{eqnarray*} P(x+1)-P(x)&=&a_n(x+1)^n-a_nx^n+[ n-1次以下の項のみ ] \\ &=&a_n(nx^{n-1}+\cdots)+[ n-1次以下の項のみ ] \end{eqnarray*}$$

となるので，$n$次整式$P(x)$に対して$P(x+1)-P(x)$は$n-1$次以下の整式である．

$Q(x)=P(x+1)-P(x)$とおく． $Q(x)$は$n-1$次以下で

$$Q(0)=P(1)-P(0),\ \cdots,\ Q(n-1)=P(n)-P(n-1)$$

がすべて整数となるので数学的帰納法の仮定から， 任意の整数$l$に対して$Q(l)$は整数である．

任意の整数$k$に対して$P(k)$が整数であることを示す． $0\le k\le n$なら条件から整数．

$k>n$のとき．$k=n+l$とおくと

$$\begin{eqnarray*} P(k)&=&P(n+l)-P(n+l-1)+P(n+l-1)-P(n+l-2)\\ &&\quad \quad +\cdots+P(n+1)-P(n)+P(n)\\ &=&Q(n+l-1)+\cdots+Q(n)+P(n) \end{eqnarray*}$$

より整数である．$k<0$のとき．$k=-l$とおく．

$$\begin{eqnarray*} P(k)&=&P(0)-P(0)+P(-1)-P(-1)+P(-2)\\ &&\quad \quad -\cdots-P(-l+1)+P(-l)\\ &=&P(0)-Q(-1)-\cdots-Q(-l) \end{eqnarray*}$$

より整数である． つまり，$n$のときにも命題が成立した． よって命題はすべての負でない整数$n$に対して成立する．□

解法2

0以上の整数 $l$ に対し

$$\begin{eqnarray*} &&u_l(x)=\dfrac{x(x-1)\cdots (x-l+1)}{l!}\quad (l \ge 1のとき)\\ &&u_0(x)=1 \end{eqnarray*}$$

とおく．

0以上の整数$n$に対し， $n$次多項式 $P(x)$ は適当な実数 $c_0,\ c_1,\ \cdots,\ c_n$ を用いて

$$P(x)= c_0 u_0(x)+ c_1 u_1(x)+\cdots+ c_n u_n(x) \quad \cdots\maru{1}$$

と表される． これを$n$に関する帰納法で示す．

$n=0$ のとき． $P(x)=a$とすると$u_0(x)=1$ なので$c_0=a$で $P(x)=c_0u_0(x)$となる．

$n-1$ 以下のとき成立しているとする． $P(x)$ の $x^n$ の係数を $a_n$ とする． $c_n=n!a_n$ とおく．このとき

$$c_nu_n(x)=n!a_n\dfrac{x(x-1)\cdots (x-n+1)}{n!} =a_nx^n+[n-1次以下の項]$$

となるので

$$P(x)-c_nu_n(x)$$

は $n-1$ 次以下の整式である． 従ってこれは $c_0(x),\ \cdots ,\ c_{n-1}(x)$ で表せる． この結果，$P(x)$ は $c_0(x),\ \cdots ,\ c_n(x)$ で表せることが示された． よって任意の $n$ に対して題意が成立した．

以下，$P(x)$は$\maru{1}$のように表されているとする． $0\le k\le n$の範囲の$k$に対して$P(k)$がすべて整数のとき， $c_0,\ c_1,\ \cdots,\ c_n$が整数であることを数学的帰納法で示す．

$P(0)=c_0$より$c_0$は整数．

$k<m$のとき$u_m(k)=0$であるから整数$k$に対して

$$\begin{eqnarray*} P(k)&=&c_ku_k(k)+\cdots+c_iu_i(k)+\cdots+c_0u_0(l)\\ &=&c_k\c... ..._{k-1}{}_k\mathrm{C}_{k-1}\cdots +c_i{}_k\mathrm{C}_i+\cdots+c_0 \end{eqnarray*}$$

となるので， $c_0,\ c_1,\ \cdots,\ c_{k-1}$が整数なら$c_k$も整数である． よって， $c_0,\ c_1,\ \cdots,\ c_n$整数であることがわかる．

このとき，任意の整数$k$に対して$P(k)$が整数であることを示す． $0\le k\le n$なら条件から整数． $k>n$ なら $u_l(k)={}_k\mathrm{C}_l$なので

$$P(k)=c_n{}_k{\rm C}_n+c_{n-1}{}_k{\rm C}_{n-1}+\cdots +c_0$$

となる．よって $P(k)$ は整数値である．

$k<0$ のとき $k=-m$ とすると

$$u_l(k)=\dfrac{(-l)(-m-1)\cdots (-m-l+1)}{l!}=(-1)^l{}_{m+l-1} {\rm C}_l$$

なので，やはり$P(k)$は整数値をとる．□

解法3

$n$次多項式$P(x)$の$n+1$個の値 $P(0),\ P(1),\ \cdots,\ P(n)$ を用いて$n$次式$f(x)$を

$$\begin{eqnarray*} f(x)&=& P(0)\cdot\dfrac{(x-1)(x-2) \cdots (x-n)}{(0-1)(0-2) \c... ...ts (x-(n-1))}{(n-0)(n-1) \cdots (n-(n-1))} \quad \cdots\maru{2} \end{eqnarray*}$$

と定める．$0\le k\le n$に対して

$$f(k)=P(k)\cdot\dfrac{(k-0)\cdots (k-(k-1))(k-(k+1)) \cdots(k-n)} {(k-0)\cdots(k-(k-1))(k-(k+1)) \cdots (k-n)}=P(k)$$

である．

$f(x)$と$P(x)$は $n+1$個の相異なる$x$の値 $x=0,\ 1,\ \cdots,\ n$ において同一の値 $P(0),\ P(1),\ \cdots,\ P(n)$をとる. 両式とも$x$の$n$次式であるから, $f(x)=P(x)$は恒等式である．

よって$\maru{2}$の右辺は$P(x)$そのものである． $P(x)$のこの表示を用いて， $0\le k\le n$の$k$に対して$P(k)$が整数のとき， $k<0,\ n<k$の$k$に対しても$P(k)$が整数であることを示す．

そのためには各項 $\dfrac{(x-0)\cdots (x-(i-1))(x-(i+1)) \cdots(x-n)} {(i-0)\cdots(i-(i-1))(i-(i+1)) \cdots (i-n)}$に $x=k$を代入した値が整数であればよい．

$k>n$のとき．

$$\begin{eqnarray*} &&\dfrac{(k-0)\cdots (k-(i-1))(k-(i+1)) \cdots(k-n)} {(i-0)\cd... ...&=&(-1)^{n-i}{}_k \mathrm{C}_i\cdot{}_{k-(i+1)} \mathrm{C}_{n-i} \end{eqnarray*}$$

$k<0$のとき．$k=-l$とおくと

$$\begin{eqnarray*} &&\dfrac{(-l-0)\cdots (-l-(i-1))(-l-(i+1)) \cdots(-l-n)} {(i-0... ... &=&(-1)^i{}_{l+i-1} \mathrm{C}_i\cdot{}_{n+l} \mathrm{C}_{n-i} \end{eqnarray*}$$

これらはいずれも整数である． したがって$\maru{2}$の各項に$k$を代入したものがすべて整数となり， $P(k)$は整数値をとる．□

吟味

解法2は

$$\begin{eqnarray*} u_l(x+1)-u_l(x) &=&\dfrac{x(x-1)\cdots (x-l+1)}{l!}-\dfrac{(x-... ...l!}\\ &=&\dfrac{(x-1)\cdots \{x-1-(l-1)+1\}}{(l-1)!}=u_{l-1}(x) \end{eqnarray*}$$

という事実を利用して $f(x)$ の次数に関する帰納法で示すこともできる．

解法2の証明をよく見れば，
　(1)の条件： $k+1$ 連続整数で $f(x)$ が整数値を取ること
　(2)の条件： $c_0(x),\ \cdots ,\ c_k(x)$ がすべて整数であること
の同値性を直接示すこともできる．

次: 直接計算か漸化式か 上: 数学的帰納法か直接証明か 前: 有理数値関数［02京大後期理系改題］