Давайте чуть-чуть продолжим про Кощея?

Так вот — похожее решение получается, если, уже придя к соотношению (*) выше,
L_{n+1} >= 2L_n - L_{n-4} - L_{n-5} - L_{n-6} -…,
начать доказывать нижнюю оценку на рост числа L_n разрешённых мелодий длины n, что
L_{n+1} >= L_n + L_{n-1}. (**)
(С той логикой, что последовательность явно будет расти медленнее, чем геометрическая со знаменателем 2, ну и Фибоначчи-подобный рост вполне хороший кандидат на попробовать…)

Доказывать — по индукции по всем меньшим значениям n. А именно: мы хотим проверить, что
L_{n+1} - L_n - L_{n-1} >=0.
А из (*) следует, что эта разность не меньше
L_n-L_{n-1}-L_{n-4}-L_{n-5}-L_{n-6}-….

Первая разность L_{n}-L_{n-1} не меньше L_{n-2} по предположению индукции. Осталось
L_{n-2}-L_{n-4}-L_{n-5}-L_{n-6}-… .
Теперь подчёркнутая разность L_{n-2}-L_{n-4} не меньше L_{n-3} по предположению индукции. Осталось
L_{n-3}-L_{n-5}-L_{n-6}-L_{n-7}… .
Теперь подчёркнутая разность L_{n-3}-L_{n-5} не меньше L_{n-4} по предположению индукции. Осталось
L_{n-4}-L_{n-6}-L_{n-7}-L_{n-8}… .
Теперь подчёркнутая разность L_{n-4}-L_{n-6} не меньше L_{n-5} по предположению индукции. Ну и так далее.

(Именно это решение рассказывали на видео-разборе; картинка-скриншот оттуда.)