文字aとbをいくつか並べた列のうちで、bが隣り合わないものだけを考える。文字がn個並んだものを「長さ

文字aとbをいくつか並べた列のうちで、bが隣り合わないものだけを考える。文字がn個並んだものを「長さnの列」と呼ぶとき…
(1)長さ3の列，長さ4の列はそれぞれ何通りあるか。
(2)長さ5の列で，aから始まる列は何通りあるか。また、長さ5の列で，bで始まる列は何通りあるか。
(3)長さnの列の個数をf(n)とするとき，f(n+2)=f(n+1)+f(n)が成り立つことを示せ。

(1)
長さ3の列は5通り
aaa，baa，aba，aab，baab
長さ4の列は8通り
aaaa，baaa，abaa，aaba，aaab，abab，baba，baab

(2)
長さ5の列で，aで始まる列は
長さ4の列の先頭にaを付けるから8通り
長さ5の列で，bで始まる列は
長さ3の列でbaを付ける(4の列の前にbをつけて数えると、先頭のb以降がbaaa，baba，baabの場合を除く必要がある)から5通り
(3)がわからない。
解説にはこう書いてあります。
長さ(n+2)の列のうち，
aで始まる列は，長さ(n+1)の列の前にaを付けたもの
bで始まる列は，長さnの列の前にbaを付けたもの
である。
したがって、f(n+2)=f(n+1)+f(n)

「したがって」がいったい何にしたがっているのか。

No.1 回答者： masterkoto 回答日時： 2020/04/16 14:40

（２）が（３）の具体例です

（２）は　n+2=5(n=3,n+1=4）の場合ですが、f(n+2)=f(5)に限定せずに拡張したものが(3)です
f(n+2)のうちbで始まるものは必ずba○○○・・・
となりますがこれは文字数n+2なので、この「○○○・・・」部分の並びは文字数nこ　ということになります
文字ｎこの並べ方の総数は、この問題ではf(n)通りとすることになっていますから
○○○・・・の先頭にbaを付け加えたものの総数も　f(n)通りです

次に、f(n+2)のうちaで始まるものは必ずa△△△△・・・
となりますがこれは文字数n+2なので、この「△△△△・・・」部分の並びは文字数n+1こ　ということになります
文字n+1個の並べ方は　nをn+1に置き換えて　f(n+1)通りですから
△△△△・・・の先頭にaを付け加えたものの総数も　f(n+1)通りです

文字数n+2この並びの内訳は、先頭がaであるものと、ｂaであるものの2種類に分かれているので
これらを合計して　f(n+2)=f(n+1)+f(n) となります

No.2 回答者： ゼロプライム 回答日時： 2020/04/16 20:15

「長さｎの列」は、「a で始まる列」と「ｂで始まる列」があります。

「長さｎの列」の個数を求めますが、「a で始まる列」の個数と「ｂで始まる列」の個数をそれぞれ求めてたし算します。

（２）で「長さ５の列」を求めましたが、「a で始まる列」の個数８と「ｂで始まる列」の個数５を足して、8+5=13（個）です。
「a で始まる列」の個数８は、「長さ４の列」８個の先頭に a を付けたものなので8個です。
「b で始まる列」の個数５は、「長さ３の列」５個の先頭に ba を付けたものなので5個です。

「長さ５の列」の個数13＝「長さ4の列」の個数８+「長さ３の列」の個数５　が成り立ちます。
　f(5)=f(4)+f(3) が成り立ちます。

同じように考えると、
「長さ(n+2)の列」は、「a で始まる列」と「ｂで始まる列」がありますが、
「長さ(n+1)の列」の先頭に a を付けたものと「長さｎの列」の先頭に ba を付けたものです。
よって、「長さ(n+2)の列」の個数は、「長さ(n+1)の列」の個数と「長さｎの列」の個数を足したものです。
したがって、f(n+2)=f(n+1)+f(n)　が成り立ちます。