Рекуррентные соотношения: от Фибоначчи до характеристического уравнения

Скажите вслух: 1, 1, 2, 3, 5, 8, 13… Любой продолжит. Числа Фибоначчи — самый известный пример задания последовательности не формулой от номера, а правилом «следующий складывается из двух предыдущих». Такие правила окружают нас везде: лестницу из $n$ ступеней можно пройти шагами в одну или две ступеньки, у дерева файлов рекурсивно растёт число ветвей, у каждого рекурсивного алгоритма есть своя формула времени работы. Как из такого самоссылочного правила вытащить явную формулу — вопрос этого урока.

Что такое рекуррентное соотношение#

Рекуррентное соотношение — формула, выражающая каждый член последовательности через предыдущие: $a_n=a_{n-1}+a_{n-2}$, $a_n=2a_{n-1}$, $a_n=n\cdot a_{n-1}$. Соотношение само по себе ничего не задаёт: к нему нужны начальные условия — первые один или два члена. Факториал живёт по правилу $a_n=n\cdot a_{n-1}$ с началом $a_0=1$ (см. словарную статью факториал); Фибоначчи — по правилу $F_n=F_{n-1}+F_{n-2}$ с началом $F_0=0$, $F_1=1$. Правило плюс начальные условия — и последовательность определена однозначно.

Проверим на лестнице. Человек поднимается по ступенькам, делая шаги на одну или две ступени. Сколько способов подняться на $n$-ю ступень? Обозначим число способов $f(n)$. Последний шаг — либо с ступени $n-1$, либо с $n-2$, других вариантов нет, значит $f(n)=f(n-1)+f(n-2)$. Начало: $f(1)=1$, $f(2)=2$. Дальше правило считает само: $f(3)=3$, $f(4)=5$, $f(5)=8$, $f(6)=13$. Рекуррента — естественный язык задач, где новое состояние собирается из предыдущих; тот же ход мысли ведёт и к деревьям рекурсии в алгоритмах.

Линейные однородные рекурренты: главная техника#

Основной класс курса — линейные однородные соотношения с постоянными коэффициентами: $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}$, где $c_1,c_2$ — числа, и никакого «довеска» отдельно от членов. Идея решения красива до неприличия: попробуем найти решения вида $a_n={\lambda }^n$ — чистые степени. Подставляем:

Сократив на ${\lambda }^{n-2}$, получаем характеристическое уравнение ${\lambda }^2-c_1\lambda -c_2=0$. Каждое его решение $\lambda$ даёт последовательность ${\lambda }^n$, послушно выполняющую рекурренту. Дальше работает линейность: если ${\lambda }_1^n$ и ${\lambda }_2^n$ — решения, то и любая комбинация $A{\lambda }_1^n+B{\lambda }_2^n$ — тоже. Константы $A$ и $B$ подбираются по начальным условиям.

Фибоначчи в буквах

Для $F_n=F_{n-1}+F_{n-2}$ характеристическое уравнение: ${\lambda }^2=\lambda +1$, то есть ${\lambda }^2-\lambda -1=0$. Корни: $\phi =\frac{1+\sqrt{5}}{2}$ — золотое сечение — и $\psi =\frac{1-\sqrt{5}}{2}\approx -0,618$. Общая форма $F_n=A{\phi }^n+B{\psi }^n$; подстановка $F_0=0$ и $F_1=1$ даёт $A=\frac{1}{\sqrt{5}}$, $B=-\frac{1}{\sqrt{5}}$:

Проверим на $n=5$: ${\phi }^5\approx 11,0902$, ${\psi }^5\approx -0,0902$, разность $11,1803$, делённая на $\sqrt{5}\approx 2,2361$, даёт ровно $5$ — и действительно, $F_5=5$. Второй корень по модулю меньше единицы, его вклад быстро тает, поэтому $F_n$ растёт как ${\phi }^n/\sqrt{5}$: например, $F_{10}=55$, а ${\phi }^{10}/\sqrt{5}\approx 55,004$. Вот зачем всё затевалось: из рекурренты вытащена формула, из формулы — скорость роста.

Когда корень один

Дискриминант может обнулиться. Для соотношения $a_n=6a_{n-1}-9a_{n-2}$ характеристическое уравнение ${\lambda }^2-6\lambda +9=0$ имеет двойной корень $\lambda =3$. Одной степенью $3^n$ тут не обойтись — второе независимое решение приносит множитель $n$: общая форма $a_n=(A+Bn){\lambda }^n$. Решим до конца при начальных условиях $a_0=1$, $a_1=2$ — это классический экзаменационный номер, пройдите его по шагам.

Порядок выше второго: лестница из трёх шагов

Техника не привязана к двойке. Пусть теперь шагать можно на одну, две или три ступени: тогда $f(n)=f(n-1)+f(n-2)+f(n-3)$ — последний шаг был с одной из трёх соседних ступенек. Начальных условий уже три: $f(1)=1$, $f(2)=2$, $f(3)=4$, и дальше правило считает само: $f(4)=7$, $f(5)=13$. Характеристическое уравнение ${\lambda }^3={\lambda }^2+\lambda +1$ — уже кубическое, и общий принцип тот же: $k$ корней (с учётом кратности) — $k$ независимых решений, комбинация из $k$ констант, подгоняемых по $k$ начальным условиям. Именно поэтому в задаче порядка $k$ без $k$ начальных членов ответ не восстановить — данных просто не хватает.

Неоднородные соотношения и башня Ханоя#

Если рядом с членами стоит добавка — соотношение неоднородное: $a_n=2a_{n-1}+1$. Стандартный приём: угадать частное решение вида добавки (для константы — константа $C$) и прибавить общее решение однородной части. Легенда задачи о Ханойской башне: чтобы перенести пирамиду из $n$ дисков, сначала переносим $n-1$ дисков на вспомогательный стержень, затем самый большой — на цель, затем пирамиду поверх него. Отсюда $a_n=2a_{n-1}+1$ с $a_1=1$.

Решение проверяется подстановкой: $a_n=2^n-1$, и правда, $a_1=1$, $a_2=3$, $a_3=7$, $a_4=15$. Число перекладываний удваивается и догоняет плюс один — экспоненциальный рост в чистом виде: для 10 дисков нужно $2^{10}-1=1023$ хода, для 64 — число, за которое легендарные монахи не управятся и за века. Заметьте экономию мысли: вместо того чтобы считать ходы руками, мы выписали правило пересчёта и свернули его в формулу — ровно та же связка «рекурсия плюс формула», что и в анализе сложности алгоритмов, о которой ниже.

1. 1
   Соотношение $a_n=a_{n-1}+n$ с $a_0=0$: добавка — не константа, а номер шага. Частное решение ищем квадратичным: $a_n^{\ast }=B{n}^2+Cn$.
2. 2
   Подстановка: $B{n}^2+Cn=B(n-1{)}^2+C(n-1)+n$. Раскрываем: $B{n}^2+Cn=B{n}^2+(-2B+C)n+(B-C)+n$.
3. 3
   Приравниваем коэффициенты: $0=-2B+1$, откуда $B=\frac{1}{2}$; $0=B-C$, откуда $C=\frac{1}{2}$.
4. 4
   Однородная часть $a_n=a_{n-1}$ даёт константу $A$; условие $a_0=0$ обнуляет её. Итог: $a_n=\frac{n(n+1)}{2}$.
5. 5
   Проверка: $a_1=1$, $a_2=3$, $a_3=6$, $a_4=10$ — треугольные числа, и каждое получается прибавлением номера шага. Сходится.

Рекурренты в анализе алгоритмов#

Где это нужно за пределами задачника? В любом рекурсивном алгоритме время работы задаётся рекуррентой. Сортировка слиянием делит массив пополам, сортирует обе половины и сливает их за $n$ операций: $T(n)=2T(n/2)+n$. Развёртка по уровням даёт ${\log }_{2}n$ уровней с линейной работой на каждом — итого $T(n)\approx n{\log }_{2}n$ (общий ответ для подобных отношений называют мастер-теоремой). Подробный язык для сравнения скоростей роста — O-нотация — живёт в соседнем уроке о сложности алгоритмов.

• Рекуррента без начальных условий не задаёт последовательность — всегда проверяйте начало
• Линейная однородная второго порядка решается через характеристическое уравнение ${\lambda }^2=c_1\lambda +c_2$
• Два разных корня → $A{\lambda }_1^n+B{\lambda }_2^n$; кратный корень → $(A+Bn){\lambda }^n$
• Неоднородное = частное решение добавки + общее однородное
• Ответ обязан проходить проверку подстановкой двух первых членов — без этого решение не засчитывается

Рекурренты — мостик между дискреткой и анализом: с одной стороны счётные задачи и комбинаторика, с другой — предельные переходы и скорости роста. Они же стоят за конечными автоматами в соответствующем уроке: переходы по шагам — та же логика состояния, зависящего от предыдущего. Размяться в пересчётах можно в тренажёре по комбинаторике.

Индукция — главный инструмент доказательства рекуррентных формул; формальное устройство базы и перехода разбирает статья математическая индукция. Механика у неё как у костяшек домино: сначала опрокидываем первую (база), затем показываем, что каждая падающая костяшка роняет следующую (переход).