C9 Рекуррентные последовательности

Идея метода: рекуррентная последовательность задаётся начальными значениями и правилом, выражающим каждый следующий элемент через предыдущие. Задача состоит в нахождении явной формулы или анализе поведения (ограниченность, периодичность, рост).

Для линейных рекуррентностей с постоянными коэффициентами ($a_{n+1} = pa_n + qa_{n-1}$) стандартный путь: написать характеристическое уравнение $r^2 = pr + q$, найти его корни $r_1, r_2$, и тогда общее решение — линейная комбинация $a_n = A r_1^n + B r_2^n$ (при различных $r_1 \neq r_2$).

Для нелинейных рекуррентностей или задач на периодичность / делимость — другие приёмы: периодичность по модулю, телескопические суммы, матричный метод.

Похожая ситуация в жизни: банковский депозит с реинвестированием — типичная рекуррентность первого порядка. Но олимпийские задачи часто добавляют «фибоначчиевую» связь между соседними элементами.

• Характеристическое уравнение. Для $a_{n+2} = p a_{n+1} + q a_n$: корни $r_1, r_2$ уравнения $r^2 = pr + q$. Если $r_1 \neq r_2$: $a_n = A r_1^n + B r_2^n$. Если $r_1 = r_2 = r$: $a_n = (A + Bn) r^n$. Условие: линейная рекуррентность второго порядка с постоянными коэффициентами. Когда использовать: когда нужна явная формула.

• Принцип периодичности по модулю. Если последовательность определяется конечным набором предыдущих элементов, то последовательность остатков по модулю $m$ периодична. Условие: рекуррентность детерминированная, область значений конечна (по модулю$). *$Когда использовать*: для задач на делимость и периодичность.

• Телескопирование. Если $a_{n+1} - a_n = f(n)$, то $a_n = a_1 + \sum_{k=1}^{n-1} f(k)$. Когда использовать: рекуррентность первого порядка с явной правой частью.

• Матричный метод. $\begin{pmatrix} a_{n+1} \\ a_n \end{pmatrix} = M \begin{pmatrix} a_n \\ a_{n-1} \end{pmatrix}$, значит $\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} = M^{n-1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix}$. Когда использовать: для быстрого вычисления $a_n$ при больших $n$ или доказательства свойств.

• Составить характеристическое уравнение и найти его корни — для линейных рекуррентностей второго порядка.
• Вычислить несколько первых членов и угадать период или закономерность, затем доказать по индукции.
• Рассмотреть остатки по модулю $m$ — доказать периодичность и найти остаток $a_n \pmod{m}$.
• Использовать телескопическую сумму: выразить $a_n - a_1$ как сумму разностей $a_{k+1} - a_k$.
• Доказать монотонность и ограниченность — тогда последовательность имеет предел, который находится из рекуррентного уравнения.
• Инвариант: найти выражение $I_n$ (функцию от $a_n, a_{n-1}$), которое не меняется при переходе $n \to n+1$.

Поверхностные признаки (что буквально написано):
- Последовательность задаётся рекуррентно: «$a_{n+1} = f(a_n)$», «$a_{n+1} = a_n + a_{n-1}$».
- «Докажите, что последовательность периодична», «найдите $a_{2024}$».
- «Докажите, что $a_n$ делится на $k$ для всех $n$».

Структурные признаки (форма выражения, объекты):
- Явно заданы $a_0, a_1$ и формула для $a_{n+1}$.
- Задача про числа Фибоначчи или похожую последовательность.
- Нужно найти сумму первых $n$ членов через рекуррентность.

Цель задачи (что от тебя хотят):
- Найти $a_n$ в явном виде.
- Доказать периодичность последовательности (или последовательности остатков).
- Доказать делимость $a_n$ на некоторое число при заданных $n$.

Задача 1. Последовательность задана: $a_1 = 1$, $a_2 = 3$, $a_{n+2} = 4a_{n+1} - a_n$. Докажите, что $a_n^2 - 3 a_{n-1} a_{n+1}$ не зависит от $n$.

Источник: тренировочная (стиль Физтех, характерный тип)

Как думать (рассуждение ученика):
1. Что я вижу? Линейная рекуррентность второго порядка, нужно исследовать выражение $I_n = a_n^2 - 3a_{n-1}a_{n+1}$.
2. Идея: проверить, что $I_{n+1} = I_n$ — то есть найти инвариант.
3. Вычислю $I_2$: $a_0 =$ ? Из $a_2 = 4a_1 - a_0$ получаю $3 = 4 - a_0$, $a_0 = 1$. $I_2 = a_2^2 - 3a_1 a_3$. $a_3 = 4 \cdot 3 - 1 = 11$. $I_2 = 9 - 3 \cdot 11 = 9 - 33 = -24$. $I_1 = a_1^2 - 3a_0 a_2 = 1 - 9 = -8$. Хм, они не совпадают... Перечитаю задачу.
4. Проверю $I_n = a_n^2 - a_{n-1}a_{n+1}$ (без тройки): $I_1 = 1 - 1 \cdot 3 = -2$. $I_2 = 9 - 1 \cdot 11 = -2$. Совпало! Докажем для $I_n = a_n^2 - a_{n-1}a_{n+1}$.

Решение:

Докажем: $a_{n+1}^2 - a_n a_{n+2} = a_n^2 - a_{n-1}a_{n+1}$.

RHS - LHS = $a_n^2 - a_{n-1}a_{n+1} - a_{n+1}^2 + a_n a_{n+2}$.

Подставим $a_{n+2} = 4a_{n+1} - a_n$:$= a_n^2 - a_{n-1}a_{n+1} - a_{n+1}^2 + a_n(4a_{n+1} - a_n)$ $= a_n^2 - a_{n-1}a_{n+1} - a_{n+1}^2 + 4a_na_{n+1} - a_n^2$ $= a_{n+1}(-a_{n-1} - a_{n+1} + 4a_n)$ $= a_{n+1}(-(a_{n+1} - 4a_n + a_{n-1})) = 0$

поскольку $a_{n+1} = 4a_n - a_{n-1}$.

Итого $I_{n+1} = I_n$, инвариант найден. Его значение $I_1 = -2$.

Ответ: $a_n^2 - a_{n-1}a_{n+1} = -2$ для всех $n \geq 1$.

Что было главным: поиск инварианта — вычисли несколько значений, угадай формулу, докажи равенство $I_{n+1} = I_n$ напрямую.

Задача 2. Докажите, что $F_n^2 + F_{n+1}^2 = F_{2n+1}$, где $F_n$ — числа Фибоначчи ($F_1 = F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$).

Источник: классическое тождество для чисел Фибоначчи (ВсОШ, различные этапы)

Как думать (рассуждение ученика):
1. Проверю для малых $n$: $n=1$: $1 + 1 = 2 = F_3$. $n=2$: $1 + 4 = 5 = F_5$. Похоже, верно.
2. Метод: индукция по $n$. База $n=1$ проверена.
3. Шаг: предположим, $F_k^2 + F_{k+1}^2 = F_{2k+1}$ и нужно доказать для $k+1$.
4. Нужно: $F_{k+1}^2 + F_{k+2}^2 = F_{2k+3}$. Знаем $F_{2k+3} = F_{2k+2} + F_{2k+1}$. Аналогично $F_{2k+2} = F_{2k+1} + F_{2k}$.
5. Используем другое тождество $F_m F_n + F_{m+1}F_{n+1} = F_{m+n+1}$ (матричный метод или индукция).

Решение (по индукции$):

*$База:* $n=1$: $F_1^2 + F_2^2 = 2 = F_3 = F_{2\cdot1+1}$. ✓

Шаг: предположим $F_n^2 + F_{n+1}^2 = F_{2n+1}$ и $F_n F_{n+1} + F_{n+1}F_{n+2} = F_{2n+2}$ (аналогичное тождество, доказывается отдельно).

$F_{n+1}^2 + F_{n+2}^2 = F_{n+1}^2 + (F_{n+1} + F_n)^2 = F_{n+1}^2 + F_{n+1}^2 + 2F_nF_{n+1} + F_n^2$ $= (F_n^2 + F_{n+1}^2) + F_{n+1}^2 + 2F_nF_{n+1}$ $= F_{2n+1} + F_{n+1}(F_{n+1} + 2F_n)$ $= F_{2n+1} + F_{n+1}(F_{n+1} + F_n + F_n)$ $= F_{2n+1} + F_{n+1} F_{n+2} + F_n F_{n+1}$ $= F_{2n+1} + F_{2n+2} = F_{2n+3}$.

Ответ: доказано по индукции.

Что было главным: индукция по $n$ + использование нескольких тождеств Фибоначчи одновременно. Стоит держать в памяти несколько базовых тождеств и подбирать нужное.

• Ошибка: находить корни характеристического уравнения, но не определять константы $A$ и $B$ из начальных условий. Почему неверно: без $A, B$ формула неполная. Как избежать: всегда подставляй $n = 0$ и $n = 1$ и решай систему для $A, B$.
• Ошибка: при двукратном корне $r_1 = r_2 = r$ писать $a_n = (A + B) r^n$ вместо $a_n = (A + Bn)r^n$. Почему неверно: нужны два линейно независимых решения. Как избежать: запомни: кратный корень всегда даёт множитель $n$.
• Ошибка: доказывать периодичность «на бумаге» без строгого обоснования. Почему неверно: нужно явно указать, что пара $(a_n \mod m, a_{n-1} \mod m)$ принимает конечное число значений, значит повторяется. Как избежать: ссылайся на принцип Дирихле.
• Ошибка: при телескопировании не проверять, что суммирование идёт по правильным индексам. Почему неверно: смещение индекса на 1 ломает всю сумму. Как избежать: явно пиши $\sum_{k=1}^{n-1}$ и проверяй граничные члены.
• Ошибка: искать предел рекуррентности, не проверяя её монотонности и ограниченности. Почему неверно: предел может не существовать, и уравнение $L = f(L)$ может иметь решение, которое не является пределом. Как избежать: сначала докажи, что последовательность монотонна и ограничена, затем бери предел.