昨年は複素数の極形式と絡めた整数問題が出題されていましたが、今年はフィボナッチ数列による記数法の問題が出題されました。「任意の正の整数は連続しないフィボナッチ数の和で一意に表すことができる。」というZeckendorfの定理が知られており、このような表し方はZeckendorf表示（「ツェッケンドルフ」や「ゼッケンドルフ」など、表記揺れがあります）と呼ばれており、たまに数学コンテストなどで取り上げられることがあります。本問は一意性に言及しない場合の出題です。
《問題》
次の条件によって定められる数列$\{a_n\}$がある。
$a_1=1$、$a_2=1$、$a_{n+2}=a_{n+1}+a_n \ (n=1,2,3,\cdots)$
以下の問いに答えよ。
（１） $2$ 以上の自然数 $n$ に対して、$a_{n+2}>2a_n$ が成り立つことを示せ。
（２）$2$ 以上の自然数 $m$ は、数列$\{a_n\}$の互いに異なる $k$ 個 $(k \geqq 2)$ の項の和で表されることを、数学的帰納法によって示せ。
（３）（２）における項の個数 $k$ は、$k<2\log_2 m+2$ を満たすことを示せ。
（九州大学2017 後期理系第５問）
《考え方》
（１）はフィボナッチ数列が増加数列であることを言えば終了です。
本命は（２）ですね。例えば $53=34+13+5+1$ ですから、実際に$$53=a_9+a_7+a_5+a_2$$と表すことができています。この式をよく見ると隣り合う2項は和の中に登場していませんね。このことは本来証明する必要が無いのですが帰納法の仮定の中に含めれば一緒に示すことができます。
$m$がフィボナッチ数であれば漸化式により帰納的に解決しますから、以下、$m$は数列$\{a_n\}$の項に一致しないものとして扱います。このとき$$a_j<m<a_{j+1} \tag{1}$$を満たすような自然数$j$が存在します。ツェッケンドルフ表示をするときには必ず$a_j$を使わなければなりません。というのも、$a_{j-1}$以下の項だけで$m$を表そうとしても
$(\ast)$「隣接する2項は使わない」
という制約があるために和が$m$まで届かないからです。そこでツェッケンドルフ表示では必ず $m=a_j+\cdots$ の形で表されるのですが、今回は$(\ast)$という指定がありません。しかしよく考えれば、フィボナッチ数列の漸化式の形から隣接する2項の和 $a_{j-1}+a_{j-2}$ を $a_{j}$ に置き換えることができるので、結局$(\ast)$が（強制的に）満たされることになります。証明の際はこの点にも少し触れておくと良いかもしれません。
さて、（２）の問題文にはどの文字に対する帰納法を使えばいいのか指示がありませんが、「$2$ 以上の（すべての）自然数 $m$ は･･･」とあるので $m$ についての帰納法を選択するのが妥当です（というかそれ以外に選択肢は考えられません）。なお、この場合の仮定は「$m$以下$2$以上のすべての自然数」に対して設定しておく必要があります。いわゆる「強化帰納法」というやつですね。
$(1)$式より、$$m-a_j=N \tag{2}$$ となるような自然数 $N$ が存在し、$N$ は $m$ よりも小さいので仮定により $N$ は複数個のフィボナッチ数列で表すことができます。
ここで$(\ast)$もついでに示しておきましょう。そのためには $N$ のツェッケンドルフ表示の中に $a_{j-1}$ が現れないことを示せばOKです（もし $N=a_{j-1}+\cdots$ と表せる場合、$(2)$式より $m=a_j+a_{j-1}+\cdots$ となって条件$(\ast)$に反してしまいます）。要するに $N \geqq a_{j-1}$ とすると$(2)$式より$$m \geqq a_{j}+a_{j-1}+\cdots=a_{j+1}+\cdots$$となって$(1)$式に反してしまいます。これは不合理なので $N < a_{j-1}$ となりますから、$N$ のツェッケンドルフ表示の中に $a_{j-1}$ が現れないことが示せました。
● ● ● ● ●
一番差が付いたのは（３）でしょう。右辺には $2\log_2 m+2$ という得体の知れないものがありますね･･･。これは何を表しているのでしょうか。その正体を暴くために $m$ について整理してみます。すると与不等式は$$m>2^{\frac{k-2}{2}} \tag{3}$$と変形できます。もし $a_j \geqq 2^{\frac{k-2}{2}}$ が成り立つのであれば、$(3)$式は$(1)$式により自動的に証明されるのですが、実はこの不等式は設問（１）で既に示しています。$a_n>2a_{n-2}$ より、$n$が奇数のとき$$\begin{align} a_n &>2a_{n-2} \\ &>2^2a_{n-4} \\ &\ \ \ \ \vdots \\ &>a_3 \cdot 2^{\frac{k-3}{2}} \\ &>2^{\frac{k-1}{2}} >2^{\frac{k-2}{2}} \end{align}$$となり、$n$が偶数のとき$$\begin{align} a_n &>2a_{n-2} \\ &>2^2a_{n-4} \\ &\ \ \ \ \vdots \\ &>a_2 \cdot 2^{\frac{k-2}{2}} >2^{\frac{k-2}{2}} \end{align}$$となるので成立しています。$a_2=1$ のとき $a_2=2^{\frac{2-2}{2}}$ となり等号が成立しますが、$m$は常に$2$以上の値しか取らないので、結局$2$以上のすべての自然数 $m$ について$(3)$式が成立することが証明できました。
よって$k$は不等式$$k<2\log_2 m+2$$を満たします。
（コメント）
今年の整数問題でも１、２を争う良問ですね。受験生にとってはかなり目新しい出題だったのではないでしょうか。数学という教科はこういう問題で差が付きやすいのです。
実は $(\ast)$「隣接する2項は使わない」という条件がツェッケンドルフ表示における一意性の根拠なのです。お暇な方は証明にチャレンジしてみて下さい。