n长的直接证明顺序

Question

我们将a（n）表示为0,1和2的n值的序列数，其中值0不能与序列中的另一个0旁边。例如，我们可以拥有（0,1,0,2），但没有（0,0,2,1）

通过直接证明n≥3

Answer 1

您可以通过以下四种方式之一构建任何长度 n（对于 n>2）的任何此类序列：

s(n-1), 1
s(n-1), 2
s(n-2), 1, 0
s(n-2), 2, 0

其中 s(n-1)是任何长度 n-1和 s(n-2)的顺序，是任何长度的 n-2。

或用文字插入；长度n（用于n>2）的序列可以是任何长度 n-1的序列，其次是1或2，或任何长度 n-2的序列，然后是1, 0或2, 0。

。

如果a(n)是该长度 n的序列的数量，则该观察结果立即给出了a(n) = 2a(n-1) + 2a(n-2)。

和完整性，a(1) = 3和a(2) = 8。