В гирлянде 31 лампочек, каждая может гореть или не гореть. Какое наибольшее возможное количество различных состояний

Возьмём для начала гирлянду из двух лампочек и рассмотрим всевозможные её состояния:Г Г; Г Н; Н Г.Всего 3 состояния.Теперь возьмём 3 лампочки:Г Г Г; Н Г Г; Г Н Г; Г Г Н; Н Г Н.Получается 5 состояний.Возьмём 4 лампочки:Г Г Г Г; Н Г Г Г; Г Н Г Г; Г Г Н Г; Г Г Г Н; Г Н Г Н; Н Г Н Г; Н Г Г Н.Получается 8 состояний.Таким образом, получим:2 лампы могут иметь 3 состояния.3 лампы могут иметь 5 состояния.4 лампы могут иметь 8 состояния.Обозначим количество лампочек в предыдущей цепи как (N - 1), а в следующей как N.Очевидно, что прибавляя каждый раз на одну лампочку больше в гирлянду, количество состояний равно сумме двух предыдущих состояний:F(N – 1) + F(N), F — состояние ламп в гирлянде.То есть, 5 лампочек в гирлянде будут иметь 8 + 5 = 13 состояний.Ряд будет выглядеть следующим образом:3, 5, 8, 13…Далее складываем 8 и 13 и так далее, продолжим ряд:3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578.Итого, 3524578 состояний лампочек в гирлянде из 31 лампочки.