bulgakov

35. Рекуррентные соотношения: что это такое

Рекуррентное соотношение задаёт последовательность правилом «каждый следующий член получается из предыдущих». Решить соотношение — найти формулу для xnx_n, не вычисляя всех предыдущих членов. Для самого простого случая xn+1=xn+f(n)x_{n+1}=x_n+f(n) формула получается сложением: xn+1=x0+f(0)+f(1)+⋯+f(n)x_{n+1}=x_0+f(0)+f(1)+\dots+f(n).

Что пригодится из прошлого: суммы вдоль диагонали треугольника Паскаля — сумма 1+2+⋯+n1+2+\dots+n; двоичные коды — число кодов удваивается с каждым местом, это пример рекуррентности. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

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

Последовательность — это числа x0,x1,x2,…x_0,x_1,x_2,\dots, выписанные по порядку. Бывает, что следующий член удобно вычислять по предыдущему:

  • в первой главе: число кодов на n+1n+1 месте вдвое больше, чем на nn местах: xn+1=2xnx_{n+1}=2x_n;
  • откладывают деньги: в каждом месяце на 100100 рублей больше, чем в предыдущем: xn+1=xn+100x_{n+1}=x_n+100.

Такое равенство называется рекуррентным соотношением. Само по себе оно не задаёт последовательность: нужен ещё начальный член (например, x0=500x_0=500), иначе подойдёт сколько угодно последовательностей.

Общий вид

Мы займёмся последовательностями, заданными условиями

xn+1=p⋅xn+f(n),x0=a,n=0,1,2,…(1)x_{n+1}=p\cdot x_n+f(n),\qquad x_0=a,\qquad n=0,1,2,\dots\tag{1}

Здесь pp — фиксированное число, aa — начальное значение, а f(n)f(n) — заданная функция: «добавка» на каждом шаге.

Решить рекуррентное соотношение значит выразить xnx_n через x0x_0, число nn и значения f(0),f(1),…,f(n−1)f(0),f(1),\dots,f(n-1) — то есть получить формулу, в которой не нужны предыдущие члены.

Вот три знакомых частных случая:

  • xn+1=xn+dx_{n+1}=x_n+d — арифметическая прогрессия (p=1p=1, f(n)=df(n)=d);
  • xn+1=q xnx_{n+1}=q\,x_n — геометрическая прогрессия (p=qp=q, f(n)=0f(n)=0);
  • xn+1=xn+(n+1)x_{n+1}=x_n+(n+1) — суммы 1+2+…1+2+\dots (p=1p=1, f(n)=n+1f(n)=n+1).

Дальше в этой и следующих главах мы разберём случаи p=1p=1 и произвольное pp, а затем соотношения, где член зависит от двух предыдущих.

Случай p=1p=1: складываем «лесенку» равенств

Пусть p=1p=1: xn+1=xn+f(n)x_{n+1}=x_n+f(n). Выпишем это соотношение для n,n−1,…,1,0n,n-1,\dots,1,0:

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)

Сложим левые и правые части всех равенств. Каждое из xn,xn−1,…,x1x_n,x_{n-1},\dots,x_1 встречается и слева, и справа — они сокращаются. Слева остаётся xn+1x_{n+1}, справа x0x_0 заменяется на aa из последней строки. Получаем

xn+1=a+∑k=0nf(k).(2)\boxed{x_{n+1}=a+\sum_{k=0}^{n}f(k)}.\tag{2}

Решение рекуррентного соотношения (1) при p=1p=1 — это начальное значение плюс сумма всех «добавок».

Как перейти к xnx_n. Формула (2) выражает xn+1x_{n+1}; чтобы получить xnx_n (при n≥1n\ge1), заменим nn на n−1n-1:

xn=a+∑k=0n−1f(k).x_n=a+\sum_{k=0}^{n-1}f(k).

Примеры

1. Арифметическая прогрессия. f(k)=df(k)=d при всех kk. Сумма nn одинаковых слагаемых dd равна ndnd, поэтому xn=a+ndx_n=a+nd. Для x0=2x_0=2, d=5d=5: x10=2+50=52x_{10}=2+50=52.

2. Квадраты. xn+1=xn+(2n+1)x_{n+1}=x_n+(2n+1), x0=0x_0=0. По формуле (2)

xn+1=∑k=0n(2k+1)=1+3+5+⋯+(2n+1)=(n+1)2,x_{n+1}=\sum_{k=0}^{n}(2k+1)=1+3+5+\dots+(2n+1)=(n+1)^2,

так что xn=n2x_n=n^2: сумма первых nn нечётных чисел равна n2n^2. Проверим:

nn 0 1 2 3 4 5 6 7 8
xnx_n по правилу 0 1 4 9 16 25 36 49 64
n2n^2 0 1 4 9 16 25 36 49 64

3. Треугольные числа. xn+1=xn+(n+1)x_{n+1}=x_n+(n+1), x0=0x_0=0. Тогда xn=1+2+⋯+n=n(n+1)2x_n=1+2+\dots+n=\dfrac{n(n+1)}2 — число (n+12)\dbinom{n+1}{2} из главы про клюшку.

Частые ошибки

  • Забыть начальное условие. Без x0x_0 решение определено лишь с точностью до слагаемого.
  • Спутать xn+1x_{n+1} и xnx_n. Сумма в (2) идёт до k=nk=n и даёт xn+1x_{n+1}; для xnx_n сумма идёт до k=n−1k=n-1.
  • Суммировать xkx_k вместо f(k)f(k). Складывают добавки ff, а не члены последовательности.
  • Считать, что f(0)f(0) пропускается. Нумерация начинается с нуля: f(0)f(0) тоже входит в сумму.

Проверь себя

1. Решите xn+1=xn+5x_{n+1}=x_n+5, x0=2x_0=2 и найдите x10x_{10}.

Решение

xn=2+5nx_n=2+5n, x10=52x_{10}=52.

2. Решите xn+1=xn+2nx_{n+1}=x_n+2^n, x0=1x_0=1.

Решение

xn=1+∑k=0n−12k=1+(2n−1)=2nx_n=1+\sum_{k=0}^{n-1}2^k=1+(2^n-1)=2^n. Сумма степеней двойки 1+2+⋯+2n−11+2+\dots+2^{n-1} равна 2n−12^n-1.

3. Решите xn+1=xn+(3n+2)x_{n+1}=x_n+(3n+2), x0=0x_0=0.

Решение

xn=∑k=0n−1(3k+2)=3⋅(0+1+⋯+(n−1))+2n=3⋅(n−1)n2+2n=n(3n+1)2x_n=\sum_{k=0}^{n-1}(3k+2)=3\cdot\bigl(0+1+\dots+(n-1)\bigr)+2n=3\cdot\dfrac{(n-1)n}2+2n=\dfrac{n(3n+1)}2. Проверка: x1=2x_1=2, x2=2+5=7=2⋅72x_2=2+5=7=\dfrac{2\cdot7}2.

4. Найдите формулу для xn+1=xn+(−1)nx_{n+1}=x_n+(-1)^n, x0=0x_0=0.

Решение

Слагаемые 1,−1,1,−1,…1,-1,1,-1,\dots: сумма nn таких слагаемых равна 11 при нечётном nn и 00 при чётном. Формула xn=1−(−1)n2x_n=\dfrac{1-(-1)^n}2.

Итог

  • Рекуррентное соотношение выражает следующий член через предыдущие; нужен начальный член.
  • Общий вид: xn+1=p xn+f(n)x_{n+1}=p\,x_n+f(n), x0=ax_0=a; решить — выразить xnx_n через x0x_0, nn и ff.
  • При p=1p=1: xn+1=a+f(0)+f(1)+⋯+f(n)x_{n+1}=a+f(0)+f(1)+\dots+f(n) — «лесенка» равенств, где промежуточные члены сокращаются.
ПрактикаЗагружаем тест…