L_nの漸化式は何ですか？ L_nは、隣接する0および2を含まずに、集合{0、1、2}からの単語を含むストリング（a_1、a_2、...、a_n）の数です。

回答：

#L_1 = 3、L_2 = 7、L_（n + 1）= 2L_n + L_（n-1） ""（n> = 2）#

説明：

最初に見つけなければなりません #L_1# そして #L_2#.

#L_1 = 3# 3つの文字列しかないので #(0) (1) (2)#.

#L_2 = 7#隣接する0と2がないすべての文字列は

#(0,0),(0,1),(1,0),(1,1),(1,2),(2,1),(2,2)#

今私達はの再発を見つけるつもりです #L_n# #（n> = 3）#.

文字列がで終わる場合 #1#、それ以降はどんな言葉でも構いません。

ただし、文字列の末尾が #0# 私達だけ置くことができます #0# または #1#.

同様に、文字列がで終わる場合 #2# 私達だけ置くことができます #1# または #2#.

みましょう #P_n、Q_n、R_n# なしの文字列の数になる #0# そして #2# 隣接する位置にあり、で終わる #0,1,2#それぞれ。

#L_n、P_n、Q_n# そして #R_n# 以下の繰り返しに従ってください。

#L_n = P_n + Q_n + R_n# （私）

#P_（n + 1）= P_n + Q_n# （ii）

#Q_（n + 1）= P_n + Q_n + R_n#(#= L_n#（iii）

#R_（n + 1）= Q_n + R_n# （iv）

（ii）、（iii）、（iv）をまとめると、 #n> = 2#:

#L_（n + 1）= P_（n + 1）+ Q_（n + 1）+ R_（n + 1）#

#= 2（P_n + Q_n + R_n）+ Q_n#

#=色（青）（2L_n）+色（赤）（L_（n-1））# （（i）と（iii）を使用）