bulgakov

37. Рекуррентные соотношения первого порядка

Чтобы решить xn+1=p xn+f(n)x_{n+1}=p\,x_n+f(n) при любом pp, запишем соотношение для n,n−1,…,0n,n-1,\dots,0 и умножим каждое равенство на подходящую степень pp: тогда промежуточные члены снова сократятся при сложении. Получается формула xn+1=a pn+1+∑k=0npkf(n−k)x_{n+1}=a\,p^{n+1}+\sum_{k=0}^{n}p^k f(n-k).

Что пригодится из прошлого: рекуррентные соотношения при p=1p=1 — «лесенка» равенств, где промежуточные члены сокращаются; бином и степени — сумма геометрической прогрессии. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Что меняется, если p≠1p\ne1

Рассмотрим снова

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

При p=1p=1 мы просто складывали равенства, и члены xn,…,x1x_n,\dots,x_1 сокращались. Если p≠1p\ne1, в соседних равенствах члены имеют разные коэффициенты (в одном xnx_n, в другом p xnp\,x_n), и простое сложение не сократит их. Исправим это умножением.

Метод: умножить и сложить

Запишем исходное соотношение xm+1=p xm+f(m)x_{m+1}=p\,x_m+f(m) для m=n, n−1, …, 1, 0m=n,\,n-1,\,\dots,\,1,\,0. Справа от каждого равенства напишем множитель, на который его умножим: у первого 11, у второго pp, у третьего p2p^2 и так далее. Последнюю строку x0=ax_0=a умножим на pn+1p^{n+1}:

x_{n+1}=p·x_n+f(n)       ×1
x_n=p·x_{n-1}+f(n-1)     ×p
x_{n-1}=p·x_{n-2}+f(n-2) ×p²
  ·  ·  ·                ·
x_2=p·x_1+f(1)           ×p^(n-1)
x_1=p·x_0+f(0)           ×p^n
x_0=a                    ×p^(n+1)

После умножения получаем:

xn+1=p xn+f(n),p xn=p2xn−1+p f(n−1),p2xn−1=p3xn−2+p2f(n−2),  ⋮pnx1=pn+1x0+pnf(0),pn+1x0=pn+1a.\begin{aligned} x_{n+1}&=p\,x_n+f(n),\\ p\,x_n&=p^2x_{n-1}+p\,f(n-1),\\ p^2x_{n-1}&=p^3x_{n-2}+p^2f(n-2),\\ &\ \ \vdots\\ p^{n}x_1&=p^{n+1}x_0+p^nf(0),\\ p^{n+1}x_0&=p^{n+1}a. \end{aligned}

Заметьте: правая часть каждого равенства содержит ту же величину, что левая часть следующего (p xnp\,x_n, затем p2xn−1p^2x_{n-1}, и так далее). Сложим все равенства: эти члены сокращаются, остаётся

xn+1=a pn+1+∑k=0npkf(n−k).(3)\boxed{x_{n+1}=a\,p^{n+1}+\sum_{k=0}^{n}p^k f(n-k)}.\tag{3}

Как читать. Первое слагаемое — начальное значение, умноженное на pn+1p^{n+1} (оно «растёт» в pp раз за каждый шаг). Каждая добавка f(n−k)f(n-k) сделана kk шагов назад и с тех пор умножилась на pp ровно kk раз. При p=1p=1 формула превращается в xn+1=a+∑f(n−k)x_{n+1}=a+\sum f(n-k) — формулу (2) из прошлой главы. Она верна и при p=0p=0: тогда считаем 00=10^0=1, и остаётся единственное слагаемое f(n)f(n), что совпадает с xn+1=f(n)x_{n+1}=f(n).

Примеры

1. Постоянная добавка (f(n)=cf(n)=c). Для p≠1p\ne1 сумма ∑k=0npk=pn+1−1p−1\sum_{k=0}^{n}p^k=\dfrac{p^{n+1}-1}{p-1} — сумма геометрической прогрессии. В этом можно убедиться, умножив её на p−1p-1: (p−1)(1+p+⋯+pn)=pn+1−1(p-1)(1+p+\dots+p^n)=p^{n+1}-1, потому что почти все слагаемые сокращаются. Поэтому

xn+1=a pn+1+c pn+1−1p−1,xn=a pn+c pn−1p−1.x_{n+1}=a\,p^{n+1}+c\,\frac{p^{n+1}-1}{p-1},\qquad x_n=a\,p^n+c\,\frac{p^n-1}{p-1}.

2. Ханойская башня. Есть три стержня и nn дисков разных размеров на одном стержне пирамидкой. Диски переносят по одному, нельзя класть больший диск на меньший. Пусть xnx_n — наименьшее число ходов, чтобы перенести nn дисков на другой стержень. Вот три стержня и три диска в начале:

     │          │          │
    ███         │          │
   █████        │          │
  ███████       │          │
стержень 1 стержень 2 стержень 3

Чтобы перенести n+1n+1 дисков, нужно сначала перенести верхние nn дисков на свободный стержень (xnx_n ходов), затем переложить самый большой диск (11 ход), затем перенести nn дисков на него (ещё xnx_n ходов):

xn+1=2xn+1,x0=0.x_{n+1}=2x_n+1,\qquad x_0=0.

Почему меньше нельзя. Самый большой диск придётся переложить хотя бы один раз. Возьмём его первый перенос: большой диск уходит со стержня, на котором лежал, на один из двух других. В этот момент все остальные nn дисков лежат на третьем стержне — ни на том, откуда уходит большой диск, ни на том, куда он идёт. Чтобы собрать их там, понадобилось не меньше xnx_n ходов (стержни равноправны, поэтому перенос nn дисков с любого стержня на любой другой требует не меньше xnx_n ходов). После последнего переноса большого диска он стоит на нужном стержне, и остальные nn дисков ещё придётся перенести на него — ещё не меньше xnx_n ходов. Эти две серии ходов не пересекаются и не содержат ходов большого диска, поэтому xn+1≥2xn+1x_{n+1}\ge2x_n+1, и найденный способ — наилучший.

Здесь p=2p=2, c=1c=1, a=0a=0: xn=2n−12−1=2n−1x_n=\dfrac{2^n-1}{2-1}=2^n-1. Для n=3n=3: 77 ходов; для n=10n=10: 10231023 ходов.

3. Утроение с добавкой. xn+1=3xn+2x_{n+1}=3x_n+2, x0=1x_0=1: p=3p=3, c=2c=2, a=1a=1:

xn=3n+2⋅3n−13−1=2⋅3n−1.x_n=3^n+2\cdot\frac{3^n-1}{3-1}=2\cdot3^n-1.

Проверка: x1=3⋅1+2=5x_1=3\cdot1+2=5 и 2⋅3−1=52\cdot3-1=5; x2=3⋅5+2=17x_2=3\cdot5+2=17 и 2⋅9−1=172\cdot9-1=17.

4. Чистый рост (f(n)=0f(n)=0). xn+1=p xnx_{n+1}=p\,x_n, x0=ax_0=a: формула даёт xn=a pnx_n=a\,p^n — геометрическая прогрессия.

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

  • Умножить не на ту степень. Множители идут 1,p,p2,…,pn1,p,p^2,\dots,p^n, а последняя строка (x0=ax_0=a) — на pn+1p^{n+1}.
  • Потерять pkp^k у добавок. Старая добавка f(n−k)f(n-k) умножается на pkp^k, а не остаётся как есть.
  • Использовать формулу геометрической прогрессии при p=1p=1. При p=1p=1 знаменатель p−1p-1 равен нулю; тогда ∑1=n+1\sum 1=n+1 (случай из прошлой главы).
  • Спутать xnx_n и xn+1x_{n+1}. Формула (3) даёт xn+1x_{n+1}; для xnx_n замените nn на n−1n-1.

Проверь себя

1. Решите xn+1=3xnx_{n+1}=3x_n, x0=5x_0=5.

Решение

xn=5⋅3nx_n=5\cdot3^n. Первые члены: 5,15,45,135,…5,15,45,135,\dots

2. Сколько ходов нужно, чтобы перенести башню из 55 дисков?

Решение

x5=25−1=31x_5=2^5-1=31.

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

Решение

p=2p=2, c=3c=3, a=1a=1: xn=2n+3⋅(2n−1)=4⋅2n−3=2n+2−3x_n=2^n+3\cdot(2^n-1)=4\cdot2^n-3=2^{n+2}-3. Проверка: x1=2⋅1+3=5=8−3x_1=2\cdot1+3=5=8-3, x2=2⋅5+3=13=16−3x_2=2\cdot5+3=13=16-3.

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

Решение

p=4p=4, c=3c=3, a=0a=0: xn=3⋅4n−14−1=4n−1x_n=3\cdot\dfrac{4^n-1}{4-1}=4^n-1. Проверка: x1=3x_1=3, x2=4⋅3+3=15=42−1x_2=4\cdot3+3=15=4^2-1.

Итог

  • Для xn+1=p xn+f(n)x_{n+1}=p\,x_n+f(n), x0=ax_0=a: умножаем равенства на 1,p,p2,…,pn1,p,p^2,\dots,p^n (последнее x0=ax_0=a — на pn+1p^{n+1}) и складываем.
  • Результат: xn+1=a pn+1+∑k=0npkf(n−k)x_{n+1}=a\,p^{n+1}+\sum_{k=0}^{n}p^kf(n-k).
  • При f(n)=cf(n)=c, p≠1p\ne1: xn=a pn+c pn−1p−1x_n=a\,p^n+c\,\dfrac{p^n-1}{p-1}; для Ханойской башни xn=2n−1x_n=2^n-1.
ПрактикаЗагружаем тест…