=====ММ38=====

**Конкурсная задача ММ8** (3 балла)

Обозначим через f(n) количество последовательностей длины n из нулей, единиц и двоек таких, что никакие две единицы и никакие две двойки не могут стоять в них подряд. Найти явную формулу для f(n).

**Решение**
 
Обозначим <m>F_0(n)</m> количество таких последовательностей, оканчивающихся на 0, <m>F_1(n)</m> - оканчивающихся на 1, <m>F_2(n)</m> - оканчивающихся на 2.\\
Тогда <m>f(n)=F_0(n)+F_1(n)+F_2(n)</m>.\\
Так как к любой последовательности можно приписать 0, не нарушив условий задачи, то
<m>F_0(n+1)= f(n) = F_0(n) + F_1(n) + F_2(n)</m>.

Так как 1 можно приписать только к последовательности, оканчивающейся на 0 или 2, то <m>F_1(n+1) = F_0(n) + F_2(n)</m>.\\
Аналогично <m>F_2(n+1) = F_0(n) + F_1(n)</m>.

Складывая, получаем:\\
<m>f(n+1) = F_0(n+1) + F_1(n+1) + F_2(n+1) = 3*F_0(n) + 2*F_1(n) + 2*F_2(n) = 2f(n) + f(n-1)</m>.

Очевидно, что f(1) = 3 и f(2) = 7.\\
Таким образом, имеем следующую рекуррентное уравнение: f(n+1) = 2f(n) + f(n-1) при n > 2, f(1) = 3, f(2) = 7.\\
Характеристическое уравнение для полученного линейного рекуррентного соотношения второго порядка имеет вид <m>x^2 - 2x - 1 = 0</m>.\\
Корни характеристического уравнения: <m>x_1 = 1 + sqrt{2}, x_2 = 1 - sqrt{2}</m>,
а общее решение - <m>f(n) =C_1{x_1}^n + C_2{x_2}^n</m>.

Учитывая начальные условия, находим:\\
<m>C_1 = {1 + sqrt{2}}/2, C_2 = {1 - sqrt{2}}/2</m>.

Окончательно имеем: <m>f(n-1) = {{(1 + sqrt{2})}^n + {(1 - sqrt{2})}^n}/2</m>.

**Обсуждение**

Последовательность, описная в обсуждаемой задаче, состоит из числителей наилучших рациональных приближений числа <m>sqrt{2}.</m>\\
С рядом других ситуаций, в которых возникает f(n), можно познакомиться в онлайн-энциклопедии математических последовательностей. Наша f(n) представлена там под номером [[http://oeis.org/A001333 | A001333]].

**Награды**

За правильное решение этой задачи Влад Франк, Мигель Митрофанов и Иван Козначеев получают по 3 призовых балла. 
----