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

この記事の所要時間: 526

問題.

次の問に答えよ.

(1) n を正の整数, a = 2^n とする. 3^a-12^{n+2} で割り切れるが 2^{n+3} で割り切れないことを示せ.

(2) m を正の偶数とする. 3^m-12^m で割り切れるならば m = 2 または m=4 であることを示せ.

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

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

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

ことをpn の両方について帰納法を使うことで示すことができます.

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

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

また,

\begin{equation*} X^s-1 = (X-1)(X^{s-1}+X^{s-2}+\cdots+X+1) \end{equation*}

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

解答例.

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

[1] n=1 のとき

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

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

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

3^{2^k}-12^{k+2} で割り切れ, 2^{k+3} で割り切れないので,

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

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

すると,

\begin{eqnarray*} 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{eqnarray*}

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

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

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

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

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

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

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

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

m = 2^r\cdot q

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

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

b = 2^r とおいて,

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

(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-12^{r+2} で割り切れ, 2^{r+3} で割り切れないことが分かりました.

3^m-12^m で割り切れるためには,

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

つまり,

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

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

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

r=1 のとき

2^r = 2,  r+2 = 3 なので, 上の不等式を満たす qq = 1 のみ,

r=2 のとき

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

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

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加