質問<1098>2003/1/29
以前、質問<1057>で 記号k>>mでk≧m+2を表すとする。 このとき、全ての正整数nは n=Fk1+Fk2+……+Fkrの形に書き表せる(*) Fkiは0<<k1<<……<<kr-1<<kr となるフィボナッチ数とする (*)は一意的に表せることの証明はどのようにすれば 示せますか?よろしくお願いします。
お便り2003/1/30
from=Tetsuya Kobayashi
こんばんは。 [補題1] F_{1}+F_{2}+...+F_{n}=F_{n+2}-1 (n: 自然数) [補題1の証明] 帰納法で示す。 I) n=1 のとき、(左辺)=(右辺)=1 で成立。 II) n=k (k≧1) のとき成立すると仮定すると、 F_{1}+F_{2}+...+F_{n}+F_{n+1}=F_{n+2}-1+F_{n+1}=F_{n+3}-1 で成立。 よって示された。 [補題1の証明終] [補題2] n を自然数とすると、F_{n+2}≧2F_{n} [補題2の証明] F_{n+2}=F_{n+1}+F_{n}≧F_{n}+F_{n}=2F_{n} [補題2の証明終] [補題3] n を自然数とすると、2F_{n+1}≧F_{n+2} [補題3の証明] 2F_{n+1}≧F_{n+1}+F_{n}=F_{n+2} [補題3の証明終] [証明] ある自然数 n が"はじめて"離散Fibonacci和で2通りに書けたとする。 このとき、n を表記するのに使われるFibonacci数列の項は、2通りに おいて同じものは存在しない。(F_{a} が共有されているとすれば、 n-F_{a} も2通りに表現できることになるから。) したがって、使用されるFibonacci数列の最大の項も異なる。 2通りの表記を n = F_{k_{1}}+F_{k_{2}}+...+F_{k_{i}} (2≦k_{1}<<k_{2}<<...<<k_{i}) = F_{l_{1}}+F_{l_{2}}+...+F_{l_{j}} (2≦l_{1}<<l_{2}<<...<<l_{j}) とすれば、k_{i}≠l_{j} である。 ここで、k_{i}>l_{j} として一般性を失わない。 また、k_{i}≧5 として問題ない。 (F_{2}=1, F_{3}=2, F_{4}=3, F_{2}+F_{4}=4 で全て異なるため。) このとき、補題1より F_{l_{1}}+F_{l_{2}}+...+F_{l_{j}}≦2F_{l_{j}}-1 であるから、F_{k_{i}}<2F_{l_{j}} となり、補題2によって k_{i}=l_{j}+1 でなければならない。このとき、 n = F_{k_{1}}+F_{k_{2}}+...+F_{k_{i-1}}+F_{l_{j}-1}+F_{l_{j}} = F_{l_{1}}+F_{l_{2}}+...+F_{l_{j}} したがって、 F_{k_{1}}+F_{k_{2}}+...+F_{k_{i-1}}+F_{l_{j}-1} = F_{l_{1}}+F_{l_{2}}+...+F_{l_{j-1}} ここで、k_{i-1}≦l_{j}-3 ならば n の最小性に反するから、 k_{i-1}≧l_{j}-2 また、k_{i}=l_{j}+1 より、 k_{i-1}≦l_{j}-1 さらに、k_{i-1}=l_{j}-2 ならば、 F_{k_{1}}+F_{k_{2}}+...+F_{k_{i-2}}+F_{l_{j}} = F_{l_{1}}+F_{l_{2}}+...+F_{l_{j-1}} となり、n の最小性に反するから、 k_{i-1}=l_{j}-1 でなければならない。このとき、 F_{k_{1}}+F_{k_{2}}+...+F_{k_{i-2}}+2F_{l_{j}-1} = F_{l_{1}}+F_{l_{2}}+...+F_{l_{j-2}}+F_{l_{j-1}} さて、補題3より、(左辺)≧F_{l_{j}} また、l_{j-2}≦l_{j-1}-2 だから、補題1より (右辺)≦2F_{l_{j-1}}-1 l_{j-1}≦l_{j}-2 だから、補題2より(右辺)≦F_{l_{j}}-1 これは矛盾である。したがって、 自然数 n の離散Fibonacci和による表現は一意的である。 [証明終]