Обозначим через f(n) количество последовательностей длины n из нулей,
единиц и двоек таких, что никакие две единицы и никакие две двойки не
могут стоять в них подряд.
Найти явную формулу для f(n).
Решение
Обозначим F0(n) количество таких последовательностей, оканчивающихся на 0,
F1(n) - оканчивающихся на 1, F2(n) - оканчивающихся на 2.
Тогда f(n)=F0(n)+F1(n)+F2(n).
Так как к любой последовательности можно приписать 0, не нарушив
условий задачи, то
F0(n+1)= f(n) = F0(n) + F1(n) + F2(n).
Так как 1 можно приписать только к последовательности, оканчивающейся на 0
или 2, то F1(n+1) = F0(n) + F2(n).
Аналогично F2(n+1) = F0(n) + F1(n).
Складывая, получаем:
f(n+1) = F0(n+1) + F1(n+1) + F2(n+1) =
3*F0(n) + 2*F1(n) + 2*F2(n)
= 2f(n) + f(n-1).
Очевидно, что f(1) = 3 и f(2) = 7.
Таким образом, имеем следующеею рекуррентное уравнение:
f(n+1) = 2*f(n) + f(n-1) при n > 2, f(1) = 3, f(2) = 7.
Характеристическое уравнение для полученного линейного рекуррентного
соотношения второго порядка имеет вид x2 - 2x - 1 = 0
.
Корни характеристического уравнения: x1 = 1 + Ö2,
x2 = 1 - Ö2,
а общее решение - f(n) =C1x1n + C2x2n.
Учитывая начальные условия, находим:
C1 = (1 + Ö2)/2, C2 = (1 - Ö2)/2.
Окончательно имеем: f(n-1) = ((1 + Ö2)n + (1 - Ö2)n)/2.
Обсуждение
Последовательность, описнная в обсуждаемой задаче, состоит из числителей
наилучших рациональных приближений числа Ö2.
С рядом других ситуаций, в которых возникает f(n), можно познакомиться
в онлайновой энциклопедии математических последовательностей. Наша f(n)
представлена там под номером A001333.
Награды
За правильное решение этой задачи Влад Франк, Мигель Митрофанов и Иван Козначеев получают по 3 призовых балла.