【東京大学入試】漸化式と整数の融合問題(2008)

(1) $$
\begin{align}
x_n&=a_n-\frac{n(n-1)}{2}p^2-np\\[1.5ex]
y_n&=b_n-n(n-1)p^2-np-1
\end{align}$$とおき, \(n=1,2,3,\cdots\)に対し\(x_n\), \(y_n\)が共に\(p^3\)で割り切れることを数学的帰納法を用いて証明する.

① \(n=1\)のとき,$$
\begin{align}
x_1&=a_1-p=p-p=0\\[1.5ex]
y_1&=b_1-p-1=p+1-p-1=0
\end{align}
$$となり, 共に\(p^3\)で割り切れるので成り立つことがわかる.

② \(n=k\)のとき成り立つと仮定して, \(n=k+1\)のとき成り立つことを示す.
\(n=k\)のとき成り立つと仮定しているので, 整数\(l\), \(m\)を用いて,$$
\begin{align}
x_k&=a_k-\frac{k(k-1)}{2}p^2-kp=lp^3\\[1.5ex]
y_k&=b_k-k(k-1)p^2-kp-1=mp^3
\end{align}
$$と表せる. これから,$$
\begin{align}
a_k&=lp^3+\frac{k(k-1)}{2}p^2+kp\\[1.5ex]
b_k&=mp^3+k(k-1)p^2+kp+1
\end{align}
$$となる.

\(n=k+1\)のとき, \(x_{k+1}\)は,$$
\begin{align}
x_{k+1}&=a_{k+1}-\frac{k(k+1)}{2}p^2-(k+1)p\\[1.5ex]
&=a_k+pb_k-\frac{k(k+1)}{2}p^2-(k+1)p\\[1.5ex]
&=lp^3+\frac{k(k-1)}{2}p^2+kp+p\left\{mp^3+k(k-1)p^2+kp+1\right\}\\[1.5ex]
&\qquad-\frac{k(k+1)}{2}p^2-(k+1)p\\[1.5ex]
&=lp^3+\frac{k^2p^2}{2}-\frac{kp^2}{2}+kp+mp^4+k^2p^3-kp^3+kp^2+p\\[1.5ex]
&\qquad-\frac{k^2p^2}{2}-\frac{kp^2}{2}-kp-p\\[1.5ex]
&=lp^3+mp^4+k^2p^3-kp^3\\[1.5ex]
&=p^3(l+mp+k^2-k)
\end{align}
$$となり, \(p^3\)で割り切れることがわかる. 次に\(y_{k+1}\)は,$$
\begin{align}
y_{k+1}&=b_{k+1}-k(k+1)p^2-(k+1)p-1\\[1.5ex]
&=pa_k+(p+1)b_k-k(k+1)p^2-(k+1)p-1\\[1.5ex]
&=p\left\{lp^3+\frac{k(k-1)}{2}p^2+kp\right\}+(p+1)\left\{mp^3+k(k-1)p^2+kp+1\right\}\\[1.5ex]
&\qquad -k(k+1)p^2-(k+1)p-1\\[1.5ex]
&=lp^4+\frac{k(k-1)}{2}p^3+kp^2+m(p+1)p^3+k^2p^3-kp^3+k^2p^2-kp^2\\[1.5ex]
&\qquad +kp^2+kp+p+1-k^2p^2-kp^2-kp-p-1\\[1.5ex]
&=p^3\left\{lp+\frac{k(k-1)}{2}+m(p+1)+k^2-k\right\}
\end{align}
$$となり, \(k\)と\(k-1\)はどちらかは偶数なので, 括弧内の\(\displaystyle \frac{k(k-1)}{2}\)は整数となり, \(y_{k+1}\)は\(p^3\)と整数をかけた形で表されるので, \(p^3\)で割り切れることがわかる.

以上から, \(n=k+1\)のときも成り立つことが示されたので, 数学的帰納法により全ての自然数\(n\)に対して, \(x_n\), \(y_n\)が\(p^3\)で割り切れることが示された.

(2) (1)から\(x_n\)に\(n=p\)を代入した数\(x_p\)は\(p^3\)で割り切れるので, 整数\(l\)を用いて\(x_p=lp^3\)と表すことができる. よってこれから, $$
x_p=a_p-\frac{p(p-1)}{2}p^2-p^2=lp^3
$$となり, \(a_p\)は$$
a_p=lp^3+\frac{p(p-1)}{2}p^2+p^2
$$と表せる. \(a_p\)を変形すると,$$
a_p=p^2\left(lp+\frac{p(p-1)}{2}+1\right)
$$となり, \(p\)は\(3\)以上の奇数なので, \(p-1\)は偶数となり, 括弧内の\(\displaystyle\frac{p(p-1)}{2}\)は整数となる. よって, \(a_p\)は\(p^2\)と整数をかけた形で表されるので, \(p^2\)で割り切れることがわかる.

また, \(a_p\)を以下のように変形する$$
a_p=p^3\left(l+\frac{p-1}{2}\right)+p^2
$$まず, \(p-1\)が偶数であることから括弧内の\(\displaystyle\frac{p-1}{2}\)は整数であり, 括弧内の数は整数となる. また, \(p\)は\(3\)以上の奇数だから, \(0<p^2<p^3\)である. よって, \(a_p\)の形から, \(a_p\)を\(p^3\)で割ったときの余りは\(p^2\)となり, \(a_p\)は\(p^3\)で割れないことがわかる.