トップ› 北海道大学› 1990年› 理系第2問

北海道大学 1990年理系第2問解説

方針・初手

(1) はすべての正の整数に関する命題であるため、数学的帰納法を利用するのが自然である。

(2) は、(1) で示した不等式と見比べると $m=n+1$ を代入した形と矛盾することに気付くのが鍵となる。$m \geqq n+1$ の範囲で条件の不等式が成り立たないことを示せばよい。

解法1

(1)

数学的帰納法を用いて証明する。

(i) $n=1$ のとき

左辺は $2^{1+1} = 4$、右辺は $1 \cdot (1+1) + 1 = 3$ となり、左辺 $>$ 右辺が成り立つ。

(ii) $n=2$ のとき

左辺は $2^{2+1} = 8$、右辺は $2 \cdot (2+1) + 1 = 7$ となり、左辺 $>$ 右辺が成り立つ。

(iii) $n=k$ ($k \geqq 2$ の整数) のとき、不等式が成り立つと仮定する。

すなわち、以下の不等式を仮定する。

$$ 2^{k+1} > k(k+1) + 1 $$

$n=k+1$ のとき、左辺から右辺を引いたものを考えると、

$$ \begin{aligned} 2^{(k+1)+1} - \{ (k+1)(k+2) + 1 \} &= 2 \cdot 2^{k+1} - (k^2 + 3k + 3) \\ &> 2 \{ k(k+1) + 1 \} - (k^2 + 3k + 3) \\ &= 2k^2 + 2k + 2 - k^2 - 3k - 3 \\ &= k^2 - k - 1 \\ &= k(k-1) - 1 \end{aligned} $$

ここで、$k \geqq 2$ であるから $k-1 \geqq 1$ となり、$k(k-1) \geqq 2 \cdot 1 = 2$ が成り立つ。

よって、$k(k-1) - 1 \geqq 1 > 0$ であるため、$n=k+1$ のときも不等式が成り立つ。

(i), (ii), (iii) より、すべての正の整数 $n$ について不等式が成り立つことが示された。

(2)

任意の正の整数 $n$ を固定して考える。

(1) の結果から、不等式 $2^{n+1} > n(n+1) + 1$ が成り立つ。これは $2^m \leqq nm+1$ において $m=n+1$ としたものが成り立たないことを示している。

そこで、$f(m) = 2^m - (nm+1)$ とおく。$m \geqq n+1$ の範囲で $f(m) > 0$ となることを示す。

(1) より、$f(n+1) > 0$ である。

また、正の整数 $m$ に対して $f(m+1) - f(m)$ を計算すると、

$$ \begin{aligned} f(m+1) - f(m) &= \{ 2^{m+1} - (n(m+1)+1) \} - \{ 2^m - (nm+1) \} \\ &= 2^{m+1} - 2^m - n \\ &= 2^m - n \end{aligned} $$

$m \geqq n+1$ のとき、$2^m \geqq 2^{n+1}$ である。(1) の不等式において右辺は明らかに $n$ より大きいため、

$$ 2^{n+1} > n(n+1) + 1 > n $$

が成り立つ。これより、$2^m > n$ すなわち $f(m+1) - f(m) > 0$ がいえる。

したがって、関数 $f(m)$ は $m \geqq n+1$ の範囲で $m$ の増加とともに単調に増加する。

$f(n+1) > 0$ であるから、$m \geqq n+1$ を満たすすべての整数 $m$ について $f(m) > 0$、すなわち $2^m > nm+1$ が成り立つ。

以上より、不等式 $2^m \leqq nm+1$ を満たす正の整数 $m$ が存在するとすれば、それは $1 \leqq m \leqq n$ の範囲に限られる。

この範囲にある正の整数は $n$ 個であるから、不等式を満たす正の整数 $m$ の個数 $a_n$ は最大でも $n$ 個である。

よって、$a_n \leqq n$ が成り立つことが示された。

解説

(1) は基本的な数学的帰納法の問題である。$n=1$ から出発して $n=k$ で仮定し $n=k+1$ を示すという標準的な手順で証明できるが、帰納法のステップにおいて $k^2-k-1 > 0$ を示す際、自然数 $k$ の範囲に注意する必要がある。$k=1$ では負となるため、$n=1, 2$ を具体的に示し、$k \geqq 2$ として帰納法を進めるのが安全かつ確実な処理である。

(2) は (1) の誘導をどう活かすかがポイントになる。(1) の不等式は $m=n+1$ における不成立を意味している。そこから「$m$ が $n+1$ 以上のときは常に不成立になるのではないか」と予想を立てることができれば、あとはそれを数式で証明するだけである。離散的な関数の大小評価においては、本解法のように数列の差分（階差）をとって単調増加性を示す手法が非常に有効である。