Число способов раскраски доски 3х3

[Ktina]

Каждую клетку доски $3\times 3$ нужно покрасить либо в белый, либо в чёрный цвет.
Сколькими способами это можно сделать так, чтобы не нашлось двух соседних по стороне белых клеток?

Кроме длинного бестолкового перебора, дающего ответ 63, не вижу никакой идеи.
Наведите, пожалуйста, на мысль.

[ИСН]

А с чего там должен быть короткий и толковый способ? С того, что получилась степень двойки минус один? Дак это небось совпадение.

[Ktina]

ИСН в сообщении #708151 писал(а):

...Дак это небось совпадение.

Вот в том-то и дело, что совпадение. Так как для доски $4\times 4$ ответ будет равен 1234.

[Sender]

Тут уже нетрудно найти эту последовательность и в OEIS.

[Ktina]

Sender в сообщении #708158 писал(а):

Тут уже нетрудно найти эту последовательность и в OEIS.

Так последовательность найти не проблема. Мне интересно, как её вычислили.

[Sender]

Ну не зря же там упомянуты числа Фибоначчи. Наверное, сначала рассмотрели одномерный случай, применив теорему Цекендорфа, а потом как-нибудь тривиально обобщили на двумерный.