京大2010年度理系[乙]第5問(数学的帰納法)

問題.

(1) は典型的な数学的帰納法の問題です.

ちなみに, この問題をより一般化して,

「正の整数 \(n, p\) に対して, \(a = p^n\) とすると, \((p+1)^a-1\) は \(p^{n+2}\) で割り切れるが \(p^{n+3}\) で割り切れない」

ことを\(p\) と\(n\) の両方について帰納法を使うことで示すことができます.

(自作問題の問題31では, \((p+1)^{p^n}\) が \(p^{n+1}\) で割り切れることを問うています. )

さて, (2) では (1)利用します. \(m\) が 2 の累乗ではなく, 偶数となっている部分を上手く処理できるかがカギですね.

また,

の変形も覚えておきましょう.

解答例.

(1) 数学的帰納法を使います.

[1] \(n=1\) のとき

\(a = 2\) で, \(3^a-1 = 8\) は\(2^{1+2} = 8\) で割り切れ, \(2^{1+3} = 16\) では割り切れない.

よって, \(n=1\) のときは成り立つ.

[2] \(n = k\) \((k\geqq 1)\)のとき成り立つと仮定すると,

\(3^{2^k}-1\) が \(2^{k+2}\) で割り切れ, \(2^{k+3}\) で割り切れないので,

\begin{align*}
3^{2^k}-1 = 2^{k+2}p
\end{align*}

と書けます (\(p\) は奇数).

すると,

\begin{align*}
3^{2^{k+1}}-1 &= (3^{2^k})^2-1\\
&= (2^{k+2}p+1)^2-1\\
&= (2^{k+2}p)^2 + 2\cdot 2^{k+2}p + 1 – 1\\
&= 2^{2k+4}p^2 + 2^{k+3}p\\
&= 2^{k+3}p(2^{k+1}+1)
\end{align*}

(指数の計算 \(3^{2^{k+1}} = (3^{2^k})^2\) となる部分を間違えないように注意しましょう!!)

ここで, \(p\) は奇数で, \(k\geqq 1\) より \(2^{k+1}+1\) も奇数なので,

\(3^{2^{k+1}}-1\) は \(2^{k+3}\) で割り切れるが \(2^{k+4}\) では割り切れない.

よって, \(n = k + 1\) のときも成り立つ.

したがって, [1], [2] より, すべての正の整数 \(n\) について

\(3^{2^n}-1\) は \(2^{n+2}\) で割り切れるが, \(2^{n+3}\) では割り切れない.

(2) (1)で証明したことを利用していきます.

\(m\) が \(2^r\) で割り切れて \(2^{r+1}\) で割り切れないような \(r\geqq 1\) を選んで,

\(m = 2^r\cdot q\)

とおきます. (\(q\) は奇数)

\(3^m-1\) が 2 で何回割り切れるかを調べます.

\(b = 2^r\) とおいて,

\begin{align*}
3^m-1 &= 3^{bq}-1\\
&= (3^b)^q – 1\\
&= (3^b-1)\{(3^b)^{q-1}+(3^b)^{q-2}+\cdots+1\}
\end{align*}

(2 行目から 3 行目の変形がカギです. )

ここで, 右辺の \(3^b-1\) は (1) の結果から, \(2^{r+2}\) で割り切れ, \(2^{r+3}\) では割り切れません.

また, \((3^b)^{q-1}+(3^b)^{q-2}+\cdots+1\) は各項は 3 の累乗なので奇数で, \(q\) 個(奇数個)　足したものなので, 奇数, つまり 2 で割り切れません.

よって, \(3^m-1\) は \(2^{r+2}\) で割り切れ, \(2^{r+3}\) で割り切れないことが分かりました.

\(3^m-1\) が \(2^m\) で割り切れるためには,

\begin{align*}
m\leqq r+2
\end{align*}

つまり,

\begin{align*}
2^rq\leqq r+2
\end{align*}

が必要十分条件になっています.

\(r \geqq 3\) のときは, \(2^r > r+2\) となることが帰納法で示されるので, \(q\geqq 1\) に対して上の不等式は成り立ちません.

\(r=1\) のとき

\(2^r = 2\),  \(r+2 = 3\) なので, 上の不等式を満たす \(q\) は \(q = 1\) のみ,

\(r=2\) のとき

\(2^r = 4\),  \(r+2 = 4\) なので, 上の不等式を満たす \(q\) は \(q = 1\) のみ, となります.

したがって, \(m\) としては \(m = 2, 4\) のみとなります.