質問＜１０５７＞２００３／１／５
from=hiroto
「帰納法」

記号ｋ＞mでｋ≧ｍ＋２を表すとする。
このとき、全ての正整数ｎは
ｎ＝Ｆk1+Ｆk2+……+Ｆkrの形に書き表せることを示せ。
ここで、Ｆkiは0＜＜k1＜＜……＜＜kr-1＜＜kr
となるフィボナッチ数とする。

フィボナッチ数列は
Ｆ1=１、Ｆ2=１、ｎ>２に対してＦn=Ｆn-2＋Ｆn-1
で定義される。

帰納法で証明するみたいなんですが分かりません。
よろしくお願いします。

お便り２００３／１／８
from=Tetsuya Kobayashi

数学的帰納法で示す。
但し、「第 k 項までの離散Fibonacci和」とは、
F_{i_{1}}+F_{i_{2}}+...+F_{i_{r}}
(0＜＜i_{1}＜＜i_{2}＜＜...＜＜i_{r}≦k)
を意味する。
--
I)
1=F_{2} より、第2項までの離散Fibonacci和で、
1≦n≦F_{3}-1(=1) なる全ての整数 n を表現可能である。
また、
1=F_{2}, 2=F_{3} より、第3項までの離散Fibonacci和で、
1≦n≦F_{4}-1(=2) なる全ての整数 n を表現可能である。
さらに、
1=F_{2}, 2=F_{3}, 3=F_{4}, 4=1+3=F_{2}+F_{4} より、
第4項までの離散Fibonacci和で、1≦n≦F_{5}-1(=4) なる
全ての整数 n を表現可能である。

II)
 k≧4 とする。
「第 k-2 項までの離散Fibonacci和で、1≦n≦F_{k-1}-1 なる
全ての整数 n を表現可能である」と仮定する。このとき、
Fibonacci数列の定義より、F_{k+1}-F_{k}=F_{k-1} である。
したがって、F_{k}+1≦n≦F_{k+1}-1 なる全ての整数 n に対
して、1≦m≦F_{k-1}-1 なる整数 m が存在して、n=F_{k}+m
を満たす。ここに m は仮定より第 k-2 項までの離散Fibonacci
和で表現可能。また、n=F_k ならば n は明らかに第 k 項まで
の離散Fibonacci和で表現可能。すなわち、第 k 項までの離散
Fibonacci和で、1≦n≦F_{k-1}-1, F_{k}≦n≦F_{k+1}-1 なる
全ての整数 n が表現可能である。
同様にして、「第 k-1 項までの離散Fibonacci和で、
1≦n≦F_{k}-1 なる全ての整数 n を表現可能である」と仮定す
れば、第 k+1 項までの離散Fibonacci和で、
1≦n≦F_{k}-1, F_{k+1}≦n≦F_{k+2}-1 なる全ての整数
n が表現可能である。
つまり、上記2つの仮定による帰結は、
「第 k+1 項までの離散Fibonacci和で、1≦n≦F_{k+2}-1 なる
全ての整数 n が表現可能である」である。
--
よって示された。(∵ F_{i} は増加数列だから。)

# 「k-2, k-1 → k+1」型の帰納法ですか。初めて見ました。
# なので、初期条件が3つ必要になるんですね。
# それにしても読みづらい解答ですみません。自分でもキツい。