F(N)は、行に2つの単位を含まない長さNの行の数を示します。 F0(N)で表示し、長さがNの行に2単位を含まず、0で終わる行を示します。F1で表示します(N)長さNの行に2単位を含まず、1で終了します。
F0とF1の繰り返し式を導き出します。
F1(N)= F0(N-1)。 2つのユニットを連続して配置することはできないため、1で終わる行の数は、1の短い長さで0で終わる行の数に等しくなります。
F0(N)= F0(N-1)+ F1(N-1)。 条件に違反することなく、正しい行にゼロを追加できます。 したがって、0で終わる行の数は、1つの短い長さの行の数に等しくなります。
F0(N)= F0(N-1)+ F1(N-1)= F0(N-1)+ F0(N-2)。 したがって、F0は特定のシフトを持つフィボナッチ数列です。 F1(N)= F0(N-1)。つまり、F1はフィボナッチ数で構成され、F0に対して「遅れ」は1です。
F(N)= F0(N)+ F1(N)。 F(N)という用語は、フィボナッチ数列F0の数がフィボナッチ数列F1の数に加算されるときに取得されます。これは、その前の数です。 また、フィボナッチ数と前のフィボナッチ数の合計もフィボナッチ数です(フィボナッチ数の式による)。 したがって、
1つの行に2つの単位を含まない行の
数がフィボナッチ数になることを証明しました。 最初の2つのNのF(N)の値を決定します。F(1)= 2(2つの適切なシーケンス:「0」と「1」)、F(2)= 3(3つの適切なシーケンス:「00」、「01」 、「10」)。
