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

2017/2/23 入試問題

この記事の所要時間：約 5分26秒

問題.

次の問に答えよ.

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

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

(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 の累乗ではなく, 偶数となっている部分を上手く処理できるかがカギですね.

また,

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

$3^m-1$ が $2^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$ なので, 上の不等式を満たす $q$ は $q = 1$ のみ,

$r=2$ のとき

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

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

関連

スポンサーリンク

黒猫の三角