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

整数値関数[08東工大理特]

問題     

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


方針

1.
次数についての数学的帰納法
2.
$f(x)$を具体的に書き表す直接法1. ${}_N\mathrm{C}_n$$N$$n$次式であるが,この$N$$x$に置きかえた式を使う.
3.
$f(x)$を具体的に書き表す直接法2. ラグランジュの補間公式を用いる.


解法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$次以下で

\begin{displaymath}
Q(0)=P(1)-P(0),\ \cdots,\ Q(n-1)=P(n)-P(n-1)
\end{displaymath}

がすべて整数となるので数学的帰納法の仮定から, 任意の整数$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$ を用いて

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

と表される. これを$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$ とおく.このとき

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

となるので

\begin{displaymath}
P(x)-c_nu_n(x)
\end{displaymath}

$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$なので

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

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

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

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

なので,やはり$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$に対して

\begin{displaymath}
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)
\end{displaymath}

である.

$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)$ がすべて整数であること
の同値性を直接示すこともできる.


next up previous
次: 直接計算か漸化式か 上: 数学的帰納法か直接証明か 前: 有理数値関数[02京大後期理系改題]
Aozora Gakuen