В гирлянде 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