質問＜１０９８＞２００３／１／２９
以前、質問＜１０５７＞で 記号ｋ>>mでｋ≧ｍ＋２を表すとする。 このとき、全ての正整数ｎは ｎ＝Ｆk1+Ｆk2+……+Ｆkrの形に書き表せる(*) Ｆkiは0＜＜k1＜＜……＜＜kr-1＜＜kr となるフィボナッチ数とする (*)は一意的に表せることの証明はどのようにすれば 示せますか？よろしくお願いします。
お便り２００３／１／３０
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和による表現は一意的である。
[証明終]