Сколько 1000-значных чисел?

[Xenia1996]

S – множество всех натуральных чисел n, удовлетворяющих трём следующим условиям:
а) n – 1000-значное число;
б) все цифры n нечетны;
в) любые две соседние цифры n различаются на 2.
Найдите количество элементов S.

(источник задачи)

Ирландская математическая олимпиада.. 1997

Я попыталась угадать ответ: $8*3^{499}$, но, во-первых, я не знаю, правильный ли это ответ, во-вторых, даже если правильный, не знаю, как доказать (Фибоначчи тут не прокатывает).
Я заменила 1000-значные числа на более мелкие и получила последовательность:
$5, 8, 14, 24, 42, 72, 126, 216, ...$ (кстати, почему её нет в OEIS?), то бишь, скажем, кол-во 5-значных чисел, все цифры которых нечётны и любые две соседние цифры различаются на 2 равно 42.
Я заметила, что начиная с 4-ого члена, каждый n-ый член равен утроенному $n-2$ - ому члену.
Помогите, пожалуйста, разобраться. Заранее спасибо!

[Xaositect]

Как вариант, можно рассмотреть множества чисел, удовлетворяющих условию и заканчивающихся цифрой $x$. Тогда ваше предположение довольно просто доказывается.

[MrDindows]

Рассмотрите все чётные $n$.
Для $n=2$: (Это наши структурные пары)
$13, 31, 35, 53, 57, 75, 79, 97$
Для $n=4 $нам надо дописать к одной паре другую, посчитаем же какое количество пар мы можем дописать к каждой паре:
для $13, 53 -- 13, 57, 53$
для $31 -- 35, 31$
для $57, 97 -- 53, 57, 97$
для $35, 75 -- 75, 35, 31, 79$
для $79 -- 79,75.$
Таким образом всего $24$ варианта, в $3$ раза больше, чем было. Также нетрудно заметить, что каждая пара встретилась три раза. Тоесть в процентном соотношении чисел заканчивающихся на одинаковые пары, их опять таки поровну. Соответственно если мы будем дописывать ещё одну пару, то количество чисел опять увеличится в $3$ раза.
Вот и получили: $a_{2(n+1)}=3a_{2n}$

[hurtsy]

Xenia1996 в сообщении #381177 писал(а):

Ирландская математическая олимпиада.. 1997

$5, 8, 14, 24, 42, 72, 126, 216, ...$ Я заметила, что начиная с 4-ого члена, каждый n-ый член равен утроенному $n-2$ - ому члену.

Доказывайте свою гипотезу по индукции. Если называть числа одной длины поколениями, можно использовать $1\mapsto 3; 3\mapsto(1,5); 5\mapsto(3,7);7\mapsto(5,9); 9\mapsto7 $. Во втором поколении $1\mapsto(1,5); 3\mapsto(3,3,7);5\mapsto(1,5,5,9); 7\mapsto(3,7,7); 9\mapsto(5,9)$. С уважением,