Алгоритмы рекуррентных соотношений

Решение рекуррентных соотношений

Будем говорить, что рекуррентное соотношение имеет порядок $$k$$, если оно позволяет выразить $$f(n + k)$$ через $$f(n),f(n + 1),\ldots,f(n + k - 1)$$. Например,$$f(n + 2) = f(n)f(n + 1) - 3f^2 (n + 1) + 1$$ рекуррентное соотношение второго порядка, а$$f(n + 3) = 6f(n)f(n + 2) + f(n + 1)$$ - рекуррентное соотношение третьего порядка. Если задано рекуррентное соотношение $$k$$ -го порядка, то ему удовлетворяет бесконечно много последовательностей. Дело в том, что первые $$k$$ элементов последовательности можно задать совершенно произвольно - между ними нет никаких соотношений. Но если первые $$k$$ элементов заданы, то все остальные элементы определяются совершенно однозначно - элемент $$f(k + 1)$$ выражается в силу рекуррентного соотношения через $$f(1),\ldots,f(k)$$ элемент $$f(k + 2)$$ - через $$f(2),\ldots,f(k + 1)$$ и т.д.

Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, причем рано или поздно получим любой ее член. Однако при этом придется выписать и все предыдущие члены - ведь не узнав их, мы не узнаем и последующих членов. Но во многих случаях нужно узнать только один определенный член последовательности, а остальные не нужны. В этих случаях удобнее иметь явную формулу для $$n$$ -го члена последовательности. Некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется. Например, последовательность$$2,4,8,\ldots,2^n,\ldots$$ является одним из решений рекуррентного соотношения$$f(n + 2) = 3f(n + 1) - 2f(n).$$ В самом деле, общий член этой последовательности имеет вид $$f(n) = 2^n$$. Значит, $$f(n + 2) = 2^{n + 2},f(n + 1) = 2^{2n + 1}$$. Но при любом $$n$$ имеет место тождество $$2^{n + 2} = 3 \cdot 2^{n + 1} - 2 \cdot 2^n$$. Поэтому $$2^n$$ является решением указанного соотношения.

Решение рекуррентного соотношения $$k$$ -го порядка называется общим, если оно зависит от $$k$$ произвольных постоянных $$C_1,C_2,\ldots,C_k$$ и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения$$f(n + 2) = 5f(n + 1) - 6f(n)$$ общим решением будет$$f(n) = C_1 2^n + C_2 3^n.$$ В самом деле, легко проверить, что последовательность (8.2) обращает (8.1) в тождество. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде (8.2). Но любое решение соотношения (8.1) однозначно определяется значениями $$f(1)$$ и $$f(2)$$. Поэтому нам надо доказать, что для любых чисел $$a$$ и $$b$$ найдутся такие значения $$C_1$$ и $$C_2^{}$$, что$$2C_1 + 3C_2 = a$$ и$$2^2 C_1 + 3^2 C_2 = b.$$ Но легко видеть, что при любых значениях $$a$$ и $$b$$ система уравнений$$2C_1 + 3C_2 = a$$ $$4C_1 + 9C_2 = b$$ имеет решение. Поэтому (8.2) действительно является общим решением соотношения (8.1).

Линейные рекуррентные соотношения с постоянными коэффициентами

Для решения рекуррентных соотношений общих правил, вообще говоря, нет. Однако существует весьма часто встречающийся класс соотношений, решаемый единообразным методом. Это - рекуррентные соотношения вида$$f(n + k) = a_1 f(n + k - 1) + a_2 f(n + k - 2) + \ldots + a_k f(n),$$ где $$a_1,a_2,\ldots,a_k$$ - некоторые числа. Такие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами.

Сначала рассмотрим, как решаются такие соотношения при $$k = 2$$, то есть изучим соотношение вида$$f(n + 2) = a_1 f(n + 1) + a_2 f(n).$$ Решение этих соотношений основано на следующих двух утверждениях.

Из утверждений 1 и 2 вытекает следующее правило решения линейных рекуррентных соотношений второго порядка с постоянными коэффициентами.

Пусть дано рекуррентное соотношение$$f(n + 2) = a_1 f(n + 1) + a_2 f(n)$$ Составим квадратное уравнение$$r^2 = a_1 r + a_2,$$ которое называется характеристическим для данного соотношения. Если это уравнение имеет два различных корня $$r_1,r_2$$, то общее решение соотношения (8.5) имеет вид$$f(n) = C_1 r_1^{n - 1} + C_2 r_2^{n - 1}.$$

Чтобы доказать это правило, заметим сначала, что по утверждению 2 $$f_1 (n) = r_1^{n - 1},f_2 (n) = r_2^{n - 1}$$ являются решениями нашего соотношения. А тогда по утверждению 1 и $$C_1r_1^n+C_2r_2^n$$ является его решением. Надо только показать, что любое решение соотношения (8.5) можно записать в этом виде. Но любое решение соотношения второго порядка определяется значениями $$f(1),f(2)$$. Поэтому достаточно показать, что система уравнений$$C_1 + C_2 = a, \hfill$$ $$C_1 r_1 + C_2 r_2 = b \hfill$$ имеет решение при любых $$a,b$$. Этими решениями являются$$C_1 = \frac{{b - ar_2 }}{{r_1 - r_2 }},$$ $$C_2^{} = \frac{{ar_1 - b}}{{r_1 - r_2 }}.$$ (Случай, когда оба корня уравнения (8.6) совпадут друг с другом, разберем в следующем пункте.)

Пример на доказанное правило.

При изучении чисел Фибоначчи мы пришли к рекуррентному соотношению$$f(n) = f(n - 1) + f(n - 2).$$ Для него характеристическое уравнение имеет вид$$r^2 = r + 1.$$ Корнями этого квадратного уравнения являются числа$$r_1 = \frac{{1 + \sqrt 5 }}{2},\quadr_2 = \frac{{1 - \sqrt 5 }}{2}.$$ Поэтому общее решение соотношения Фибоначчи имеет вид$$f(n) = C_1 (\frac{{1 + \sqrt 5 }}{2})^n + C_2 (\frac{{1 - \sqrt 5 }}{2})^n.$$ (Мы воспользовались сделанным выше замечанием и взяли показатели $$n$$ вместо $$n - 1$$ ). Мы называли числами Фибоначчи решения соотношения (8.7), удовлетворяющее начальным условиям $$f(0) = 1,f(1) = 2$$ ( то есть последовательность $$1, 2, 3, 5, 8, 13, ..$$.). Часто бывает более удобно добавить к этой последовательности вначале числа 0 и 1, то есть рассматривать последовательность $$0, 1, 1, 2, 3, 5, 8 13,..$$. Ясно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению (8.6) и начальным условиям $$f(0) = 1,f(1) = 2$$. Полагая в формуле (8.8) $$n = 0,n = 1$$, получаем для $$C_1^{},C_2$$ систему уравнений$$C_1 + C_2 = 0$$ $$\hfill \frac{{\sqrt 5 }} {2}(C_1 - C_2 ) = 1 \hfill$$ Отсюда находим, что $$C_1=-C_2=\frac{1}{\sqrt 5}$$ и потому$$f(n) = \frac{1}{\sqrt 5 }[(\frac{{1 + \sqrt 5 }} {2})^n - (\frac{{1 - \sqrt 5 }}{2})^n ].$$ На первый взгляд кажется удивительным, что это выражение при всех натуральных значениях $$n$$ принимает целые значения.

Случай равных корней характеристического уравнения

Рассмотрим случай, когда оба корня характеристического уравнения совпадают: $$r_1 = r_2$$. В этом случае выражение $$C_1 r_1^{n - 1}+ C_2 r_2^{n - 1}$$ уже не будет общим решением. Ведь из-за того, что $$r_1 = r_2$$, это решение можно записать в виде$$f(n) = (C_1 + C_2 )r_1^{n - 1} = Cr_1^{n - 1}.$$ Остается только одно произвольное постоянное ; и выбрать его так, чтобы удовлетворить двум начальным условиям $$f(1) = a,f(2) = b$$, вообще говоря, невозможно.Поэтому надо найти какое-нибудь второе решение, отличное от $$f_1 (n) = r_1^{n - 1}$$. Таким решением является $$f_2 (n) = nr_1^{n - 1}$$. В самом деле, если квадратное уравнение $$r^2 = a_1 r + a_2$$ имеет два совпадающих корня $$r_1 = r_2$$, то по теореме Виета $$a_1 = 2r_1,a_2 = - r_1^2$$. Поэтому уравнение записывается так:$$r^2 = 2r_1 r - r_1^2.$$ А тогда рекуррентное соотношение имеет такой вид:$$f(n + 2) = 2r_1 f(n + 1) - r_1^2 f(n).$$ Проверим, что $$f_2 (n) = nr_1^{n - 1}$$ действительно являются его решением. Имеем $$f_2 (n + 2) = (n + 2)r_1^{n + 1}$$, а $$f_2 (n + 1) = (n + 1)r_1^n$$. Подставляя эти значения в соотношение (8.10), получаем очевидное тождество$$(n + 2)r_1^{n + 1} = 2(n + 1)r_1^{n + 1} - nr_1^{n + 1}.$$

Значит, $$nr_1^{n - 1}$$ - решение рассматриваемого соотношения.

Итак, имеются два решения $$f_1 (n) = r_1^{n - 1}$$ и $$f_2 (n) = nr_1^{n - 1}$$ заданного соотношения. Его общее решение запишется так:$$f(n) = C_1 r_1^{n - 1} + C_2 nr_1^{n - 1} = r_1^{n - 1} (C_1 + C_2 n).$$ Теперь уже путем подбора $$C_1, C_2$$ можно удовлетворить любым начальным условиям.

Линейные рекуррентные соотношения с постоянными коэффициентами, порядок которых больше двух, решаются таким же способом. Пусть соотношение имеет вид$$f(n + k) = a_1 f(n + k - 1) + \ldots + a_n f(n).$$ Составим характеристическое уравнение$$r^k = a_1 r^{k - 1} + \ldots + a_k.$$ Если все корни $$r_1,r_2,\ldots,r_k$$ этого алгебраического уравнения $$k$$ -й степени различны, то общее решение соотношения (8.3) имеет вид$$f(n) = C_1 r_1^{n - 1} + C_2 r_2^{n - 1} + \ldots + C_k r_k^{n - 1}.$$ Если же, например, $$r_1 = r_2 = \ldots = r_s$$, то этому корню соответствуют решения$$f_1 (n) = r_1^{n - 1},f_2 (n) = nr_1^{n - 1},$$ $$f_3 (n) = n^2 r_1^{n - 1},\ldots,f_s (n) = n^{s - 1} r_1^{n - 1}$$ рекуррентного соотношения (8.11). В общем решении этому корню соответствует часть$$r_1^{n - 1} [C_1 + C_2 n + C_3 n^2 + \ldots + C_s n^{s - 1} ]$$

Составляя такое выражение для всех корней и складывая их, получаем общее решение соотношения (8.3).

Например, решим рекуррентное соотношение$$f(n + 4) = 5f(n + 3) - 6f(n + 2) - 4f(n + 1) + 8f(n).$$ Характеристическое уравнение в этом случае имеет вид$$r^4 - 5r^3 + 6r^2 + 4r - 8 = 0.$$ Решая его, получим корни$$r_1 = 2,r_2 = 2,r_3 = 2,r_4 = - 1.$$ Значит, общее решение нашего соотношения имеет следующий вид:$$f(n) = 2^{n - 1} [C_1 + C_2 n + C_3 n^2 ] + C_4 ( - 1)^{n - 1}.$$

Производящие функции

В комбинаторных задачах на подсчет числа объектов при наличии некоторых ограничений искомым решением часто является последовательность $$a_0,a_{1,},a_2,\ldots$$, где $$a_k$$ - число искомых объектов "размерности" $$k$$. Например, если мы ищем число разбиений числа, то можем принять $$a_k = P(k)$$, если ищем число подмножеств $$n$$ -элементного множества, то $$a_k =(_k^n)$$ и т.д. В этом случае удобно последовательности $$a_0,a_{1,},a_2,\ldots$$, поставить в соответствие формальный ряд$$A(x) = \sum\limits_{k = 0}^\infty {a_k x^k },$$ называемый производящей функцией для данной последовательности. Название формальный ряд для данной последовательности означает, что (8.12) мы трактуем только как удобную запись нашей последовательности - в данном случае несущественно, для каких (действительных или комплексных) значений переменной $$x$$ он сходится. Поэтому мы никогда не будем вычислять значение такого ряда для конкретного значения переменной $$x$$, мы будем только выполнять некоторые операции на таких рядах, а затем определять коэффициенты при отдельных степенях переменной $$x$$. Для произвольных рядов$$A(x) = \sum\limits_{k = 0}^\infty {a_k x^k,B(x) = \sum\limits_{k = 0}^\infty {b_k x^k } }$$ мы определим операцию сложения:$$A(x) + B(x) = \sum\limits_{k = 0}^\infty {(a_k + b_k )x^k },$$ операцию умножения на число (действительное или комплексное):$$pA(x) = \sum\limits_{k = 0}^\infty {pa_k x^k }$$ и произведение Коши$$A(x) \cdot B(x) = \sum\limits_{k = 0}^\infty {c_k x^k },$$ где$$c_k = a_0 b_k + a_1^{} b_{k - 1} + \ldots + a_k b_0 = \sum\limits_{i = 0}^k {a_i b_{k - i} },$$ Если $$a_k = 0$$ для $$k > n$$, то ряд (8.12) будем отождествлять с многочленом $$a_n x^n + \ldots + a_0$$. Из математического анализа известно, что если ряд (8.12) сходится в некоторой окрестности нуля, то его сумма $$A(x)$$ является аналитической функцией в этой окрестности и$$a_k = A^{(k)} (0)/k!,k = 0,1,2,\ldots$$ ( $$A^{(k)} (0)$$ обозначает значение $$k$$ -й производной функции $$A(x)$$ для $$x = 0$$ ; ряд 8.12 - это не что иное, как ряд Маклорена функции $$A(x)$$ ). Более того, когда $$A(x),B(x)$$ являются аналитическими функциями в окрестности нуля, то формулы (8.13)-(8.16) будут справедливы, если $$A(x),B(x)$$ трактовать как значения функций $$A,B$$ в точке $$x$$, а ряды понимать в обычном смысле, т.е. так, как в математическом анализе. Это сохраняющее операции взаимно однозначное соответствие между рядами, сходящимися в окрестности нуля, и функциями, аналитическими в окрестности нуля, позволяет отождествить формальный ряд (8.12) с определенной через него аналитической функцией в случае рядов, сходящихся в окрестности нуля (несмотря на то, что ряды мы будем трактовать всегда как формальные ряды, то есть только как формальную запись их коэффициентов). Таким образом, будем писать, например,$$\sum\limits_{k = 0}^\infty {x^k = (1 - x)^{ - 1} },$$ $$\sum\limits_{k = 0}^\infty {\frac{1}{{k!}}x^k = e^x }$$ и т.д.