L_n的递推公式是什么？ L_n是字符串（a_1，a_2，...，a_n）的数量，其中来自集合{0,1,2}的单词没有任何相邻的0和2。

回答：

#L_1 = 3，L_2 = 7，L_（n + 1）= 2L_n + L_（n-1）“”（n> = 2）#

说明：

首先我们必须找到 #L_1# 和 #L_2#.

#L_1 = 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 （ⅱ）

#Q_（N + 1）= + P_N + Q_N#R_n(#=#L_N）（iii）

#R_（N + 1）= + Q_N#R_n （ⅳ）

总结（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））