[別館]球面倶楽部零八式markIISR

東大入試数学中心。解説なので解答としては不十分。出題年度で並ぶようにしている。大人の解法やうまい解法は極めて主観的に決めている。

2017年(平成29年)九州大学後期-数学(理系)[5]

次の条件によって定められる数列 $\{a_n\}$ がある．
$a_1=1，a_2=1，a_{n+2}=a_{n+1}+a_n（n=1，2，3，\ldots）$
以下の問いに答えよ。

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

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

(3) (2) における項の個数 $k$ は， $k\lt 2\log_2 m+2$ を満たすことを示せ．

2021.01.08記
自然数のフィボナッチ表現（ゼッケンドルフ表示）。

自然数のフィボナッチ表現は2倍取りゲームやワイトホフの2山崩しの必勝法を説明するときに登場する．

ただ、本問は正確にはフィボナッチ表現ではない．例えば、 $8$ のフィボナッチ表現は $a_6$ であるが、本問 (2) においては、
$8=a_6=a_5+a_4=a_5+a_3+a_2=a_5+a_3+a_1$ のように一意性をみたさないからである．

以下、解答例を載せておくが、 $a_1=a_2$ であることから、細かい議論（工夫）が必要になってくる．

(1) $n\geqq 2$ で $a_n$ は単調増加だから、 $2a_n\lt a_n+a_{n+1}=a_{n+2}$ より成立．

(2) (a) $m=2$ のとき、 $m=a_2+a_1$ より成立する．

(b) $2\leqq m\leqq i$ について成立すると仮定する．

このとき $i\geqq 2$ により、 $2=a_3\leqq a_{j+1}\leqq i \leqq a_{j+2}-1$ なる $j\geqq 2$ が存在するので，
$m=i+1$ のとき、 $1\leqq m-a_{j+1} \leqq a_{j+2}-a_{j+1}=a_{j}\lt a_{j+1}$ が成立する．

$m-a_{j+1} =1$ のとき， $m=a_1+a_{j+1}$ （ $j+1\neq 1$ ）と異なる2個の項の和で表現できる．

$2\leqq m-a_{j+1}\leqq a_j$ となりうるのは $a_j\geqq 2$ 、つまり $j\geqq 3$ のときであり，この場合は、仮定より、 $a_1$ から $a_{j-1}$ のうちの少くとも2つの和で表現できるので， $i+1$ は3個以上の項の和で表現できる．

以上から、 $m=i+1$ のときも題意は成立するので、よって数学的帰納法により，2以上の任意の自然数 $m$ について題意は成立する．

(3) $2^{\frac{k}{2}-1} \lt m$ を示せば良い．

ここで， $a_{k} \lt m \leqq a_{k+1}$ をみたすとき， $m$ は $a_1,\ldots,a_k$ のうちの2個以上 $k$ 個以下の和で表すことができるので、 $a_k \geqq 2^{\frac{k}{2}-1}$ を示せば良い．

(a) $k$ が2以上の偶数 $2s$ のとき $a_{2s}>2^{s-1} a_2=2^{s-1}>2^{\frac{k}{2}-1}$ より成立．

(b) $k$ が3以上の奇数 $2s+1$ のとき $a_{2s+1}>2^{s-1} a_3=2^{s}=2^{\frac{k-1}{2}}>2^{\frac{k}{2}-1}$ より成立．

よって題意は成立する．

あんまり美しくないので、そのうち改良したい．

2022.10.22記
2倍取りゲームについては
数学談話室倍取りゲーム(pdf)
石取りゲームとFibonacci数
あたりを参照すれば良いだろう．