n長さの直接証明シーケンス

Question

値0がシーケンス内の別の0の次にあり得ない0,1,2のn個の値のシーケンスの数としてa（n）を示します。 たとえば、（0,1,2,2）はありませんが、（0,0,2,1）はありません。

a（n）= 2a（n-1）+ 2a （N-2）は、n≥3

Answer 1

ためのこれらの4つの方法のいずれかで一意（n>2ため）長nの任意のこのようなシーケンスを構築することができる：

s(n-1)は長 n-1の任意のそのような配列である

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

をs(n-2)は、長さがn-2の任意のそのような配列である。

または言葉で表してください。 （n>2用）長さnの配列は1又は2続く長n-1の任意の配列、又は1, 0又は2, 0続く長n-2の任意の配列とすることができます。

a(n)が長さnのこのような配列の数である場合、この観察は、必要に応じてすぐにa(n) = 2a(n-1) + 2a(n-2)を与える。

完全性のために、a(1) = 3およびa(2) = 8。