n 长度的直接证明序列

Question

我们将 a(n) 表示为 n 个值 0,1 和 2 的序列数，其中值 0 不能与序列中的另一个 0 相邻。例如，我们可以有 (0,1,0,2)，但不能有 (0,0,2,1)

直接证明 a(n) = 2a(n-1) + 2a(n-2) 对于 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。

Direct proof sequence of n length