質問<1057>2003/1/5
記号k>mでk≧m+2を表すとする。 このとき、全ての正整数nは n=Fk1+Fk2+……+Fkrの形に書き表せることを示せ。 ここで、Fkiは0<<k1<<……<<kr-1<<kr となるフィボナッチ数とする。 フィボナッチ数列は F1=1、F2=1、n>2に対してFn=Fn-2+Fn-1 で定義される。 帰納法で証明するみたいなんですが分かりません。 よろしくお願いします。
お便り2003/1/8
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つ必要になるんですね。 # それにしても読みづらい解答ですみません。自分でもキツい。