Заметим, что в такой последовательности единица может идти только после 0 и 2, а 0 и 2 могут идти после любого числа. Будем поддерживать кол-во последовательностей текущей длины которые заканчиваются на 1, и кол-во последовательностей текущей длины заканчивающихся на 0 или 2. Постепенно будем последовательность "достраивать"

Пример кода на python:
n = int(input())
edin = 1 #1 последовательность длины один ("1"), заканч. на 1. -- база динамики
nonedin = 2 #2 последовательности длины один ("0", "2"), заканч. на 0 или 2
for i in range(2, n + 1): #перебираем длину последовательности, от 2 до n
    edin += nonedin, nonedin += edin + nonedin #единицу можем приписать только к не единицам, не единицы к любым
print(edin + nonedin)