九州大学 2017年度後期・理系数学後期第5問解答・解説

問題

次の条件によって定められる数列 ${a_{n}}$ がある。

a_{1} = 1, a_{2} = 1, a_{n + 2} = a_{n + 1} + a_{n} (n = 1, 2, 3, \dots\dots)

以下の問いに答えよ。

(1) 2以上の自然数 $n$ に対して， $a_{n + 2} > 2 a_{n}$ が成り立つことを示せ。

(2) 2以上の自然数 $m$ は，数列 ${a_{n}}$ の互いに異なる $k$ 個 $(k ≧ 2)$ の項の和で表されることを，数学的帰納法によって示せ。

(3) (2)における項の個数 $k$ は， $k < 2 lo g_{2} m + 2$ を満たすことを示せ。

出典：九州大学 2017年度後期日程第2次学力試験後期・理系後期第5問

方針

解法1

フィボナッチ型数列の基本性質を使う。(1)は $n ≧ 2$ で $a_{n + 1} > a_{n}$ を確認してから示す。(2)は $m$ に関する帰納法で， $m$ 以下の最大の項 $a_{n}$ を取り，残り $r = m - a_{n}$ が $a_{n - 1}$ 未満になることを使う。 $m = a_{n}$ の場合も $a_{n} = a_{n - 1} + a_{n - 2}$ で2項に分ける。(3)は(1)から $a_{j} ≧ 2^{(j - 2) /2}$ を導き， $k$ 個の異なる項の最大添字が少なくとも $k$ であることから項数を評価する。

解法2

(1)は単調増加性から示す。(2)は $m$ 以下の最大の項を選ぶ貪欲法を強い帰納法として記述する。(3)は添字を2つ進めるごとの増加率から最大添字を評価する。

解答

解法1

(1)

まず $n ≧ 2$ では数列は増加していることを確認する。実際， $a_{2} = 1 < a_{3} = 2$ であり，その後は $a_{n + 1} = a_{n} + a_{n - 1} > a_{n}$ が成り立つ。したがって $n ≧ 2$ では $a_{n + 1} > a_{n}$ である。よって $a_{n + 2} = a_{n + 1} + a_{n} > 2 a_{n}$ が成り立つ。

(2)

$m$ に関する数学的帰納法で示す。 $m = 2$ のときは $2 = a_{1} + a_{2}$ であり，互いに異なる2個の項の和で表される。 $2, 3, \dots, m - 1$ について主張が成り立つと仮定し， $m$ について示す。 $m$ 以下の最大の項を $a_{n}$ とする。すなわち $a_{n} ≦ m < a_{n + 1}$ である。

もし $m = a_{n}$ なら， $m ≧ 2$ より $n ≧ 3$ であり $a_{n} = a_{n - 1} + a_{n - 2}$ だから， $m$ は互いに異なる2個の項の和で表される。

次に $m > a_{n}$ とする。このとき $r = m - a_{n}$ とおくと， $r > 0$ である。また $m < a_{n + 1} = a_{n} + a_{n - 1}$ より $r < a_{n - 1}$ である。 $r = 1$ なら $m = a_{n} + a_{1}$ と表せる。ここで $n ≧ 3$ なので， $a_{n}$ と $a_{1}$ は異なる項である。 $r ≧ 2$ なら，帰納法の仮定により， $r$ は互いに異なる2個以上の項の和で表される。しかも $r < a_{n - 1}$ であるから，その表現に $a_{n - 1}$ 以上の項は現れない。したがって，そこに $a_{n}$ を加えても項は重ならず， $m$ は互いに異なる項の和で表される。以上で帰納法が完了した。

(3)

(1)より，添字を2つ進めるごとに値は2倍より大きくなる。特に $j ≧ 2$ について $a_{j} ≧ 2^{(j - 2) /2}$ が成り立つ。これは $j = 2, 3$ で直接確かめられ，その後は(1)を繰り返せばよい。 $m$ を互いに異なる $k$ 個の項の和で表したとする。この $k$ 個の項の中で最大の添字を $r$ とすると，異なる添字が $k$ 個あるので $r ≧ k$ である。したがって最大の項は少なくとも $a_{k}$ 以上である。また和 $m$ は最大の項だけでなく他の正の項も含むので $m > a_{k}$ である。よって $m > a_{k} ≧ 2^{(k - 2) /2}$ となる。両辺の $2$ を底とする対数をとると $lo g_{2} m > \frac{k - 2}{2}$ であるから $k < 2 lo g_{2} m + 2$ が成り立つ。

解法2

(1)

$n ≧ 2$ では $a_{n + 1} > a_{n}$ である。したがって

a_{n + 2} = a_{n + 1} + a_{n} > 2 a_{n} .

(2)

$m$ に関する強い帰納法を用いる。 $m = 2$ は $a_{1} + a_{2}$ と表せる。 $2 ≦ r < m$ で主張が成り立つと仮定し， $a_{n} ≦ m < a_{n + 1}$ となる最大の項 $a_{n}$ を取る。

$m = a_{n}$ なら

m = a_{n - 1} + a_{n - 2}

でよい。 $m > a_{n}$ なら $r = m - a_{n}$ とおく。 $m < a_{n + 1} = a_{n} + a_{n - 1}$ より $0 < r < a_{n - 1}$ である。 $r = 1$ なら $m = a_{n} + a_{1}$ ， $r ≧ 2$ なら帰納法の仮定で $r$ を互いに異なる項の和にできる。その各項は $a_{n - 1}$ より小さいため $a_{n}$ と重ならない。よって主張が成り立つ。

(3)

(1)を繰り返すと

a_{j} ≧ 2^{(j - 2) /2} (j ≧ 2) .

$m$ を異なる $k$ 項の和で表したとき，最大添字は少なくとも $k$ である。さらに最大項以外にも正の項があるので

m > a_{k} ≧ 2^{(k - 2) /2} .

底2の対数を取れば

k < 2 lo g_{2} m + 2.

九州大学 2017年度後期・理系数学 後期 第5問

問題

方針

解法1

解法2

解答

解法1

(1)

(2)

(3)

解法2

(1)

(2)

(3)

九州大学 2017年度
後期・理系数学後期第5問