В гирлянде 29 лампочек, каждая может гореть или не гореть. Какое наибольшее возможное количество различных состояний может быть у гирлянды, если в ней не могут быть выключенными две соседние лампочки? Например, у гирлянды из двух лампочек три возможных состояния: обе горят; первая горит, а вторая не горит; первая не горит, а вторая горит.

Например, пусть в гирлянде имеется n лампочек, необходимо обозначить выключенную лампочку как 0, а включенную как 1. Нам необходимо найти число f (n) возможных гирлянд, для которого два нуля не будут идти подряд. Исходя из этого, f1=2 и f2=3, при условии, что n>=3. Состояния лапочек оканчивается или на 1, либо на 10, а перед этим записывается состояние гирлянды, длина которой n-1 или n-2, где два нуля не встречается.

Следовательно, здесь необходимо применить рекуррентную формулу f (n) = f (n-1) + f (n-2) при n>=3.

Следует, что это числа Фибоначчи, т. е. каждое следующее равно сумме двух предыдущих. Вычисляем число 31, оно равно 3524578