35. Рекуррентные соотношения: что это такое
Рекуррентное соотношение задаёт последовательность правилом «каждый следующий член получается из предыдущих». Решить соотношение — найти формулу для , не вычисляя всех предыдущих членов. Для самого простого случая формула получается сложением: .
Что пригодится из прошлого: суммы вдоль диагонали треугольника Паскаля — сумма ; двоичные коды — число кодов удваивается с каждым местом, это пример рекуррентности. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Последовательность и правило
Последовательность — это числа , выписанные по порядку. Бывает, что следующий член удобно вычислять по предыдущему:
- в первой главе: число кодов на месте вдвое больше, чем на местах: ;
- откладывают деньги: в каждом месяце на рублей больше, чем в предыдущем: .
Такое равенство называется рекуррентным соотношением. Само по себе оно не задаёт последовательность: нужен ещё начальный член (например, ), иначе подойдёт сколько угодно последовательностей.
Общий вид
Мы займёмся последовательностями, заданными условиями
Здесь — фиксированное число, — начальное значение, а — заданная функция: «добавка» на каждом шаге.
Решить рекуррентное соотношение значит выразить через , число и значения — то есть получить формулу, в которой не нужны предыдущие члены.
Вот три знакомых частных случая:
- — арифметическая прогрессия (, );
- — геометрическая прогрессия (, );
- — суммы (, ).
Дальше в этой и следующих главах мы разберём случаи и произвольное , а затем соотношения, где член зависит от двух предыдущих.
Случай : складываем «лесенку» равенств
Пусть : . Выпишем это соотношение для :
x_{n+1} = x_n + f(n)
x_n = x_{n-1} + f(n-1)
x_{n-1} = x_{n-2} + f(n-2)
· · ·
x_2 = x_1 + f(1)
x_1 = x_0 + f(0)
x_0 = a
───────────────────────────────
x_{n+1} = a + f(0) + … + f(n)
Сложим левые и правые части всех равенств. Каждое из встречается и слева, и справа — они сокращаются. Слева остаётся , справа заменяется на из последней строки. Получаем
Решение рекуррентного соотношения (1) при — это начальное значение плюс сумма всех «добавок».
Как перейти к . Формула (2) выражает ; чтобы получить (при ), заменим на :
Примеры
1. Арифметическая прогрессия. при всех . Сумма одинаковых слагаемых равна , поэтому . Для , : .
2. Квадраты. , . По формуле (2)
так что : сумма первых нечётных чисел равна . Проверим:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| по правилу | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 |
| 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 |
3. Треугольные числа. , . Тогда — число из главы про клюшку.
Частые ошибки
- Забыть начальное условие. Без решение определено лишь с точностью до слагаемого.
- Спутать и . Сумма в (2) идёт до и даёт ; для сумма идёт до .
- Суммировать вместо . Складывают добавки , а не члены последовательности.
- Считать, что пропускается. Нумерация начинается с нуля: тоже входит в сумму.
Проверь себя
1. Решите , и найдите .
Решение
, .
2. Решите , .
Решение
. Сумма степеней двойки равна .
3. Решите , .
Решение
. Проверка: , .
4. Найдите формулу для , .
Решение
Слагаемые : сумма таких слагаемых равна при нечётном и при чётном. Формула .
Итог
- Рекуррентное соотношение выражает следующий член через предыдущие; нужен начальный член.
- Общий вид: , ; решить — выразить через , и .
- При : — «лесенка» равенств, где промежуточные члены сокращаются.
