整数値多項式を攻略する – 1993年東工大 数学 第4問
今回取り上げるのは、 1993年東工大 数学 第4問 。整数値多項式の問題です。問題は以下の通りです。
n を自然数、 P(x) を n 次の多項式とする。このとき、
P(0),P(1),P(2), \cdot \cdot \cdot ,P(n)
がすべて整数なら、任意の整数 m に対して P(m) が整数であることを証明せよ。
多項式 P(x) が整数値多項式であるとは、任意の整数 m に対し、 P(m) が整数になるもののことを言います。
注意すべきは、整数係数多項式とは異なるということです。実際、以下の2次式は、整数係数多項式ではありませんが、整数値多項式です。
P(x) = \frac{1}{2}x^2+\frac{1}{2}x+1なお、以下の内容は、東工大が公表したものではありません。
1993年東工大 数学 第4問 の解法
オーソドックスに、多項式の次数 n に関する数学的帰納法で攻めます。
ポイントは、 (x+1)^n - x^n が n-1 次の多項式になることを利用することです。次数が1つ減るので、数学的帰納法の前提条件が利用できます。
n = 1 のとき、多項式 P(x) = a_1 x + a_0 において、 P(0) 、 P(1) がともに整数であるとします。すると、 a_0 、 a_1 はいずれも整数になるので、任意の整数 m に対し、 P(m) は明らかに整数になります。
次に、自然数 n \text{ } (1 \leqq n) において、題意が成立していると仮定します。かつ、 n+1 次の多項式 P(x) = \sum_{k=0}^{n+1} a_k x^k において、 P(0),P(1),P(2), \cdot \cdot \cdot ,P(n+1) がすべて整数であると仮定します。
ここで n 次の多項式 Q(x) を、
\begin{aligned}
Q(x) = P(x+1) - P(x) \\
= \sum_{k=0}^{n+1} a_k \{ (x+1)^k - x^k \}
\end{aligned}と定義します。このとき、帰納法の仮定により、 0 \leqq m \leqq n であるすべての整数 m に対し、 Q(m) = P(m+1)-P(m) はすべて整数になります。
したがって、同じく帰納法の仮定により、すべての整数 m に対し、 Q(m) は整数になります。
ゆえに、すべての非負整数 m に対し、 P(m+1) = Q(m) + P(m) が整数であることが、逐次的に成り立ちます。
また、すべての負の整数 m に対し、 P(m) = -Q(m) + P(m+1) が整数であることが、逐次的に成り立ちます。
別の解法
任意の n 次元の多項式が、 n+1 個の既知の整数値多項式の線形結合で表されることを利用して、証明します。
ここでは既知の整数値多項式として、 C_k(x) , k=0,1, \cdot \cdot \cdot ,n を以下のように定義します。
C_k(x) = \left \{
\begin{aligned}
& 1 & k=0\\
& \frac{1}{k!} \prod_{i=0}^{k-1} (x-i) & k>0
\end{aligned}
\right.k \geqq 1 のとき、任意の整数 m に対し、
C_k(m) = \left \{
\begin{aligned}
& {}_m C_k & m \geqq k \\
& 0 & 0 \leqq m \leqq k-1 \\
& (-1)^k {}_{k-m-1} C_k & m \leqq -1
\end{aligned}
\right.なので、 C_k(x) は確かに整数値多項式です。
C_k(x) , k=0,1, \cdot \cdot \cdot ,n は互いに線形独立なので、 n+1 次元の線形空間を張ります。したがって、任意の n 次元多項式 P(x) は、 n+1 の実数 b_0, b_1 , \cdots , b_n が一意に存在して、
P(x) = \sum_{k=0}^{n} b_k C_k(x)と表記できます。あとは P(0),P(1),P(2), \cdot \cdot \cdot ,P(n) がすべて整数であるという条件から、 b_k が整数になることを、逐次的に示していきます。
この証明方法は、「 C_k(x) の線形結合」の下りがなかなかスマートですが、高校の学習範囲でこれは必ずしも自明ではありません。
これの証明を求められるとなると、却って面倒くさいので、ここはやはり、普通に数学的帰納法で証明したほうが良いと思います。
発展
問題の内容は、多項式の値が整数値になることの証明でしたが、加法に関して閉じている集合なら、同じように証明できます。（ex. P(0),P(1),P(2), \cdot \cdot \cdot ,P(n) がすべて偶数なら、任意の整数 m に対して P(m) が偶数）
また、多項式 P(x) の独立変数の間隔が一定なら、間隔が1である必要はありません。もっと言うと、整数である必要もありません。間隔が一定ならどんな値でも、同じように証明できます。
解法のポイントと、今後の学習方針
本問は「 (x+1)^n - x^n が n-1 次の多項式になる」ということを証明に使おうと思いつくかどうかが、すべてです。
しかしこれは相当にハードルが高く、東工大の入試で実際に出題された時には正解者がほとんどなかったため、後年ＡＯ入試において、全く同じ内容で再出題されたと言われています。
したがって、整数値多項式問題の解法はそんなものだと割り切って、そのまま覚えておくしかありません。逆にこれが頭に入っていれば、整数値多項式のどんな問題も、サクッと解けることでしょう。
整数値多項式の問題は、各大学で頻繁に出題されています。問題集などでも見ることがあると思いますので、その際は今回のコツを思い出して、問題に取り組んでみてください。