37. Рекуррентные соотношения первого порядка
Чтобы решить при любом , запишем соотношение для и умножим каждое равенство на подходящую степень : тогда промежуточные члены снова сократятся при сложении. Получается формула .
Что пригодится из прошлого: рекуррентные соотношения при — «лесенка» равенств, где промежуточные члены сокращаются; бином и степени — сумма геометрической прогрессии. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Что меняется, если
Рассмотрим снова
При мы просто складывали равенства, и члены сокращались. Если , в соседних равенствах члены имеют разные коэффициенты (в одном , в другом ), и простое сложение не сократит их. Исправим это умножением.
Метод: умножить и сложить
Запишем исходное соотношение для . Справа от каждого равенства напишем множитель, на который его умножим: у первого , у второго , у третьего и так далее. Последнюю строку умножим на :
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)
После умножения получаем:
Заметьте: правая часть каждого равенства содержит ту же величину, что левая часть следующего (, затем , и так далее). Сложим все равенства: эти члены сокращаются, остаётся
Как читать. Первое слагаемое — начальное значение, умноженное на (оно «растёт» в раз за каждый шаг). Каждая добавка сделана шагов назад и с тех пор умножилась на ровно раз. При формула превращается в — формулу (2) из прошлой главы. Она верна и при : тогда считаем , и остаётся единственное слагаемое , что совпадает с .
Примеры
1. Постоянная добавка (). Для сумма — сумма геометрической прогрессии. В этом можно убедиться, умножив её на : , потому что почти все слагаемые сокращаются. Поэтому
2. Ханойская башня. Есть три стержня и дисков разных размеров на одном стержне пирамидкой. Диски переносят по одному, нельзя класть больший диск на меньший. Пусть — наименьшее число ходов, чтобы перенести дисков на другой стержень. Вот три стержня и три диска в начале:
│ │ │
███ │ │
█████ │ │
███████ │ │
стержень 1 стержень 2 стержень 3
Чтобы перенести дисков, нужно сначала перенести верхние дисков на свободный стержень ( ходов), затем переложить самый большой диск ( ход), затем перенести дисков на него (ещё ходов):
Почему меньше нельзя. Самый большой диск придётся переложить хотя бы один раз. Возьмём его первый перенос: большой диск уходит со стержня, на котором лежал, на один из двух других. В этот момент все остальные дисков лежат на третьем стержне — ни на том, откуда уходит большой диск, ни на том, куда он идёт. Чтобы собрать их там, понадобилось не меньше ходов (стержни равноправны, поэтому перенос дисков с любого стержня на любой другой требует не меньше ходов). После последнего переноса большого диска он стоит на нужном стержне, и остальные дисков ещё придётся перенести на него — ещё не меньше ходов. Эти две серии ходов не пересекаются и не содержат ходов большого диска, поэтому , и найденный способ — наилучший.
Здесь , , : . Для : ходов; для : ходов.
3. Утроение с добавкой. , : , , :
Проверка: и ; и .
4. Чистый рост (). , : формула даёт — геометрическая прогрессия.
Частые ошибки
- Умножить не на ту степень. Множители идут , а последняя строка () — на .
- Потерять у добавок. Старая добавка умножается на , а не остаётся как есть.
- Использовать формулу геометрической прогрессии при . При знаменатель равен нулю; тогда (случай из прошлой главы).
- Спутать и . Формула (3) даёт ; для замените на .
Проверь себя
1. Решите , .
Решение
. Первые члены:
2. Сколько ходов нужно, чтобы перенести башню из дисков?
Решение
.
3. Решите , .
Решение
, , : . Проверка: , .
4. Решите , .
Решение
, , : . Проверка: , .
Итог
- Для , : умножаем равенства на (последнее — на ) и складываем.
- Результат: .
- При , : ; для Ханойской башни .
