Вычисление рекуррентных соотношений

Зачем это в ЕГЭ. Задание 16 (бывшее 11) на рекуррентные соотношения — это 1 первичный балл. Проверяет умение формализовать процесс и работать с последовательностями. Встречается в 30% реальных вариантов.

Главная идея. Рекуррентное соотношение — это правило, по которому каждый следующий элемент последовательности вычисляется через предыдущие. Ключ — выписать первые несколько значений вручную, найти закономерность и перейти к общей формуле.

Алгоритм (чеклист).
1. Выписать начальные условия (обычно даны в задаче).
2. Вычислить 3-5 следующих элементов по рекуррентному правилу.
3. Искать закономерность: арифметическая/геометрическая прогрессия, периодичность, связь с номерами элементов.
4. Проверить гипотезу на вычисленных значениях.
5. Записать общую формулу или алгоритм для n-го элемента.
6. Подставить требуемое значение n и вычислить ответ.

Опоры (кратко).
- Формула n-го члена арифметической прогрессии: $a_n = a_1 + d(n-1)$
- Формула n-го члена геометрической прогрессии: $b_n = b_1 \cdot q^{n-1}$
- Периодичность: если $a_{k+p} = a_k$, период равен p
- Линейное рекуррентное соотношение: $F_n = F_{n-1} + F_{n-2}$ (числа Фибоначчи)

Пример 1 (линейное соотношение).
Дано: $a_1 = 1$, $a_2 = 2$, $a_n = 3a_{n-1} - 2a_{n-2}$. Найти $a_5$.
Шаг 1. $a_1 = 1$ (по условию).
Шаг 2. $a_2 = 2$ (по условию).
Шаг 3. $a_3 = 3 \cdot 2 - 2 \cdot 1 = 4$.
Шаг 4. $a_4 = 3 \cdot 4 - 2 \cdot 2 = 8$.
Шаг 5. $a_5 = 3 \cdot 8 - 2 \cdot 4 = 16$.

Пример 2 (периодичность).
Дано: $b_1 = 3$, $b_{n+1} = 1 - \frac{1}{b_n}$. Найти $b_{2023}$.
Шаг 1. $b_1 = 3$.
Шаг 2. $b_2 = 1 - \frac{1}{3} = \frac{2}{3}$.
Шаг 3. $b_3 = 1 - \frac{3}{2} = -\frac{1}{2}$.
Шаг 4. $b_4 = 1 - (-2) = 3$.
Шаг 5. Замечаем период 3: $b_{2023} = b_{3 \cdot 674 + 1} = b_1 = 3$.

Типичные ошибки.
1. Неверные начальные условия — подставляют n=0 вместо n=1.
2. Арифметические ошибки — теряют знаки при вычислениях.
3. Не проверяют период — останавливаются на 3-4 элементах.
4. Путают типы прогрессий — применяют формулу геометрической вместо арифметической.

Дальше. Переходи к задачам на динамическое программирование и рекурсивные алгоритмы.