Последовательности и прогрессии

Зачем это в ЕГЭ. Задание №19, 4 первичных балла. Последовательности появляются в двух видах: (1) рекуррентно заданная последовательность с вопросом о делимости/чётности/периоде; (2) сюжет типа «на доске написаны числа, каждый ход...» — по сути скрытая рекурсия. Нужно уметь выписывать первые члены, замечать закономерность и доказывать её.

Главная идея. Рекуррентная формула $x_{n+1}=g(x_n)$ задаёт последовательность; для анализа: (1) выписать первые $5$–$10$ членов, (2) заметить период или формулу, (3) доказать по индукции или через инвариант (величина, не меняющаяся при переходе). Остатки по модулю $m$ дают периодическую последовательность — это ключ к задачам на делимость.

Алгоритм (чеклист).
1. Выписать первые члены по правилу — посмотреть на чётность, остатки, рост.
2. Если видна закономерность (период, формула) — доказать её: по индукции ($P(1)$, $P(k)\Rightarrow P(k+1)$) или через инвариант.
3. Для периода остатков: выписать $x_n\bmod m$ до первого повторения пары $(x_n, x_{n+1})$ — дальше цикл гарантирован.
4. Для «игровых» сюжетов: найти инвариант (чётность суммы, остаток произведения и т.д.) — он не меняется при ходе, но в начальном и «целевом» состоянии разный $\Rightarrow$ невозможность.
5. Оценки: если члены целые, положительные и растут — оценить сверху/снизу для ответа на «найти все $n$, при которых...».

Опоры (кратко).
- АП: $a_n=a_1+(n-1)d$, $S_n=\frac{n(a_1+a_n)}{2}$.
- ГП: $b_n=b_1\cdot q^{n-1}$, $S_n=b_1\cdot\frac{q^n-1}{q-1}$.
- Период остатков Фибоначчи по mod $m$ (период Пизано) — конечен для любого $m$.
- Индукция: доказать базу, допустить для $k$, вывести для $k+1$.

Пример 1 (рекуррентность, явная формула). $x_1=1$, $x_{n+1}=2x_n+1$. Найти $x_n$.

Шаг 1. Первые члены: $1,3,7,15,31,\ldots$ Гипотеза: $x_n=2^n-1$.

Шаг 2. Проверка индукцией. База: $x_1=2^1-1=1$ — верно. Шаг: $x_{k+1}=2x_k+1=2(2^k-1)+1=2^{k+1}-1$ — верно.

Шаг 3. Ответ: $x_n=2^n-1$.

Пример 2 (период остатков). Последовательность Фибоначчи $F_1=F_2=1$, $F_{n+2}=F_{n+1}+F_n$. Доказать, что $F_n$ делится на $3$ при $n\equiv0\pmod4$.

Шаг 1. Остатки по mod $3$: $1,1,2,0,2,1,0,1,1,2,0,\ldots$ Период $8$.

Шаг 2. В позициях $4,8,12,\ldots$ (кратных $4$) остаток $0$ — делится на $3$. ЧТД.

Пример 3 (инвариант в игре). На доске числа $1,2,\ldots,10$. За ход можно стереть два числа и написать их сумму. Можно ли получить одно число, равное $56$?

Шаг 1. Сумма чисел на доске не меняется при ходе (стираем $a,b$, пишем $a+b$).

Шаг 2. Начальная сумма: $\frac{10\cdot11}{2}=55$. Финальное число $=55\ne56$. Невозможно.

Типичные ошибки.
1. Замечают закономерность, но не доказывают — «видно, что...» не засчитывается без индукции или другого обоснования.
2. Ошибка в индексах — путают $n$ и $n+1$, $a_n$ и $a_{n-1}$.
3. Предполагают АП/ГП без проверки — не всякая «красивая» последовательность арифметическая.
4. Не замечают инвариант — главный приём в задачах на «можно ли»; без него перебор бесконечен.

Дальше. Числовые наборы и полные задачи №19 в тренажёре.