Рекуррентные соотношения. Общие и частные решения рекуррентных соотношений Рекуррентное соотношение примеры

Данный метод состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, называемого рекуррентным. Говорят, что последовательность элементов u0 , u1 , … un , … над полем комплексных чисел C удовлетворяет рекуррентному соотношению порядка k, если

где a1 , … , ak - коэффициенты из C. Соотношения такого типа естественным образом возникают при решении комбинаторных задач.

Пример. Пусть имеется последовательность позиций, занумерованных числами 1, 2, … , n, … и в начальный момент предмет находится в 1-ой позиции. За один ход предмет продвигается вперед на 1 и 2 позиции. Найти число способов попадания в n-ю позицию.

♦ Пусть un - интересующее нас число. Ясно, что u2 = 1, u3 = 2 . Далее, разобьем все способы попадания в позицию с номером n на два класса: те, при которых на последнем шаге предмет передвигается на 1 шаг и те, при которых он передвигается на 2 шага. Ясно, что в первом случае имеем un-1 вариантов, во втором un-2 вариантов. Следовательно, имеем

Многочлен P(x) называется характеристическим для линейного рекуррентного соотношения (2). Заметим, что всякая рекуррентная последовательность k-го порядка однозначно определяется заданием k ее первых членов.

Пусть λ - корень характеристического многочлена P(x).

Теорема 1. Последовательность u0 , u1 , … un , … , где un = cλ n , c - произвольная константа из C, удовлетворяет линейному рекуррентному соотношению (2).

♦ Подставляя данные значения un , n = 0, 1, … в (2), имеем

cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦

Теорема 2. Пусть последовательности un , vn , n = 0, 1, … удовлетворяют линейному рекуррентному соотношению (2). Тогда этим свойством обладает последователь-

ность rn , n = 0, 1, … , где rn = α un + β vn , n , α, β - произвольные константы из C.

♦ Доказательство очевидно. ♦

Теорема 3. Пусть λ 1 , … , λ k - простые (т.е. не являющиеся кратными) корни характеристического многочлена P(x) для последовательности (2).

Тогда общее решение данного рекуррентного соотношения имеет вид

где c1 , … , ck - подходящие константы из C.

♦ Согласно предыдущему замечаем, что последовательностьun , n = 0, 1, … есть решение соотношения (2). Чтобы доказать, что любое решение имеет вид (5) достаточно показать, что для произвольной последовательности vn , n = 0, 1, … , удовлетворяющей

(2), существуют константы c1 , … , ck , такие, что un = vn , n . Для этого достаточно, чтобы выполнялось v0 = u0 , v1 = u1 , … , vk-1 = uk-1 . Рассмотрим данные условия

относительно c1 , c2 , … , ck . Определитель этой системы есть определитель Вандермонда и согласно (7, стр. 118).

согласно предположению о корнях λ 1 , … , λ k . Отсюда и следует утверждение. ♦ В качестве примера рассмотрим рекуррентное соотношение (3). Имеем характеристический многочлен

P(x) = x2 - x -1

Его корни равны λ 1 = 1 + 2 5 , λ 2 = 1 − 2 5 , Общее решение имеет вид

u n = c 1 1+ 2 5 n + c 2 1− 2 5 n

Система уравнений для констант c1 , c2 : c1 1 + 2 5 + c2 1 − 2 5 = 1

Пусть теперь λ - корень кратности r характеристического многочлена P(x). Аналогично предыдущему доказывается

Теорема 4. Последовательности c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … для про-

извольных констант c1 , … , cr из C удовлетворяют соотношению (2).

Теорема 5. Пусть характеристический многочлен P(x) имеет корни λ 1 , … , λ s кратностей r1 , … , rs (r1 + … + rs = k) . Тогда общее решение рекуррентного соотношения

Укажем еще одно полезное свойство линейных рекуррентных соотношений. Теорема 6. Пусть имеем соотношение

un = a1 un-1 + … + ak un-k

с начальными условиями u1 , … , uk . Тогда справедливо соотношение при всех n ≥ k

♦ Доказательство индукцией по n. При n = k равенство (8) справедливо. Пусть оно верно при n. При n + 1 имеем

В большинстве случаев, однако, при изучении перечислительных задач возникают нелинейные рекуррентные соотношения, для разрешения которых используются специфические приемы. Некоторые из них будут рассмотрены в дальнейшем. Приведем важный пример нелинейного рекуррентного соотношения.

Теорема 7. Пусть C(n, k) - число подстановок n-элементного множества, имеющих точно k циклов. Тогда справедливо

♦ Разобьем множество подстановок множества X = {1, 2, … n,} имеющих точно k циклов, на два класса - подстановки, в которых элемент n содержится в единичном цикле, и подстановки, в которых элемент n находится в цикле длины l, l > 1. В первом случае число подстановок совпадает с числом подстановок множества X′ = {1, 2, …, n - 1}, имеющих k - 1 циклов, т.е. C(n - 1, k - 1). Во втором случае, удаляя элемент n, полу-

чаем подстановку множества X′ = {1, 2, …, n - 1} с k циклами, число которых равно C(n - 1, k). Выясним теперь, каким числом способов в подстановку степени n - 1 с k циклами можно добавить элемент n. Если имеется цикл длины i, то это можно сделать i способами. Общее число способов равно i1 + … + ik , где i1 , … , ik - длины циклов подстановки. Однако i1 + … + ik = n - 1. Значит число подстановок второго класса равно

(n - 1)C(n - 1, k). Отсюда и получаем (9). ♦

Полученные числа C(n, k) связаны с известными числами Стирлинга первого рода sn,k , которые определяются так:

sn,k = (- 1)n+k C(n, k)

Приведем таблицу нескольких первых значений чисел sn,k .

Табл. Числа Стирлинга первого рода

Комбинаторные вычисления на конечных множествах

Введение в комбинаторику

Предметом теории комбинаторных алгоритмов, часто называемой комбинаторными вычислениями, являются вычисления на дискретных математических структурах. В этой теории большое внимание уделяется алгоритмическому подходу к решению задач дискретной математики, оптимизации перебора вариантов, сокращению числа рассматриваемых решений.

Область комбинаторных алгоритмов включает в себя задачи, которые требуют подсчёта (оценивания) числа элементов в конечном множестве или перечисления этих элементов в специальном порядке (приложение Б). При этом широко применяется процедура выбора элементов с возвращением и её варианты.

Существуют два вида задач подсчёта. В простом случае задаётся конкретное множество и требуется определить точно число элементов в нём. В общем случае имеется семейство множеств, заданное некоторым параметром, и определяется мощность множества как функция параметра. При этом часто бывает достаточной оценка порядка функции , а иногда требуется только оценка скорости её роста . Например, если мощность подлежащего рассмотрению множества растёт по некоторому параметру экспоненциально, то этого может оказаться достаточно для того, чтобы отказаться от предложенного подхода к изучению проблемы, не занимаясь различными деталями. К этому, более общему, типу проблем применяются процедуры асимптотических разложений, рекуррентных соотношений и производящих функций.

Асимптотика

Асимптота - особая линия (чаще всего прямая), являющаяся предельной для рассматриваемой кривой.

Асимптотика - это искусство оценивания и сравнения скоростей роста функций. Говорят, что при х ®¥ функция "ведёт себя, как х ", или "возрастает с такой же скоростью, как х ", и при х ®0 "ведёт себя, как 1/x ". Говорят, что "logx при x ®0 и любом e>0 ведёт себя, как x e , и что при n ®¥ растёт не быстрее, чем n logn ". Такие неточные, но интуитивно ясные утверждения полезны при сравнении функций так же, как и соотношения <, £ и = при сравнивании чисел.

Определим три основных асимптотических соотношения.

Определение 1. Функция f (x ) эквивалентна g (x ) при х ®x 0 , если и только если =1.

В этом случае говорят, что функция f (x ) асимптотически равна функции g (x ) или что f (x ) растёт с такой же скоростью, как и g (x ).

Определение 2 . f (x )=o(g (x )) при x ®x 0 , если и только если =0.

Говорят, что при x ®x 0 f (x ) растёт медленнее, чем g (x ), или что f (x ) "есть о-малое" от g (x ).

Определение 3. f (x )=О(g (x )) при x ®x 0 , если и только если существует константа С такая, что sup =С.

В этом случае говорят, что f (x ) растёт не быстрее, чем g (x ), или что при x ®x 0 f (x ) "есть О-большое" от g (x ).

Cоотношение f (x )=g (x )+o (h (x )) при x ®¥ означает, что f (x)-g (x )=o (h (x )). Аналогично f (x )=g (x )+О (h (x )) означает, что f (x )-g (x )=О (h (x )).

Выражения О(·) и о(·) могут использоваться также и в неравенствах. Например, неравенство x +o (x )£2x при x ®0 означает, что для любой функции f (x ) такой, что f (x )=o (x ), при x ®¥ имеет место соотношение x+f (x )£2x для всех достаточно больших значений х .

Приведём некоторые полезные асимптотические равенства.

Полином асимптотически равен своему старшему члену:

при x ®¥; (4.1)

при x ®¥; (4.2)

при x ®¥ и a k ¹0. (4.3)

Суммы степеней целых чисел удовлетворяют соотношению:

при n ®¥. (4.4)

Отсюда, в частности, имеем при n ®¥

В более общем случае при n ®¥ и для любого целого k ³0

; (4.6)

. (4.7)

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

Понятие рекуррентных соотношений проиллюстрируем на классической проблеме, поставленной и изученной Фибоначчи около 1200 г.

Фибоначчи поставил свою проблему в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара кроликов становится фертильной (fertile – плодовитый) через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается. Пусть F n - число пар кроликов в популяции по прошествии n месяцев и пусть эта популяция состоит из N n пар приплода и O n “старых” пар, т.е. F n = N n + O n . Таким образом, в очередном месяце произойдут следующие события:

Старая популяция в (n +1)-й момент увеличится на число родившихся в момент времени n , т.е. O n+1 = O n + N n = F n ;

Каждая старая в момент времени n пара производит в момент времени (n +1) пару приплода, т.е. N n+1 = C n .

В последующий месяц эта картина повторяется:

O n+2 = O n+1 + N n+1 = F n+1 ,

N n+2 = O n+1 ;

объединив эти равенства, получим рекуррентное соотношение Фибонначи:

O n+2 + N n+2 = F n+1 + O n+1 ,

F n+2 = F n+1 + F n . (4.8)

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенные свойства этой последовательности определяются рекуррентным соотношением (4.8). Обычно полагают F 0 =0, F 1 =1 (иногда полагают F 0 =F 1 =1).

Рекуррентное соотношение (4.8) является частным случаем однородных линейных рекуррентных соотношений с постоянными коэффициентами:

x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k , (4.9)

где коэффициенты a i не зависят от n и x 1 , x 2 , …, x k считаются заданными.

Существует общий метод решения (т.е. отыскания x n как функции n ) линейных рекуррентных соотношений с постоянными коэффициентами. Этот метод рассмотрим на примере соотношения (4.8). Найдём решение в виде

F n =cr n (4.10)

с постоянными с и r . Подставляя это выражение в (4.8), получим

cr n + 2 = cr n+ 1 + cr n ,

cr n (r n -r -1)=0. (4.11)

Это означает, что F n =cr n является решением, если либо с =0, либо r = 0 (и отсюда F n =0 для всех n ), а также (и это более интересный случай) если r 2 - r -1=0, причём константа с произвольна. Тогда из (4.11) следует

r = или r = . (4.12)

Число »1,618 известно как ²золотое² сечение, поскольку с древних времен считается, что треугольник (прямоугольник) со сторонами 1 и имеет наиболее приятные для глаза пропорции.

Сумма двух решений однородного линейного рекуррентного соотношения, очевидно, также является решением, и можно на самом деле показать, что общее решение последовательности Фибоначчи имеет вид

F n = , (4.13)

где константы с и с’ определяются начальными условиями. Положив F 0 =0 и F 1 =1, получим следующую систему линейных уравнений:

, (4.14)

решение которой даёт

c = -c" = . (4.15)

В математике весьма часто употребляют такие термины как «рекурсивные функции», «рекуррентные последовательности», «рекуррентные соотношения», «рекурсивные алгоритмы». Все эти термины имеют один корень, происходящий от латинского слова гесиггеге - возвращаться. Общим для рекурсивных функций, рекурсивных алгоритмов и рекуррентных последовательностей является то, что для вычисления очередного значения функции, получения очередной реализации алгоритма, определения очередного члена последовательности необходимо обращаться к предшествующим их значениям, вычисленным раньше. В свою очередь, вычисление предшествующих значений требует обращения к вычисленным перед этим требуемым значениям и т.д. Таким образом, для того чтобы получить значение функции, реализацию алгоритма или значение члена ряда на п-м шаге необходимо знать их значения на (п - 1)-м шаге, а следовательно, на первом шаге. Правило, которое определяет способ вычисления очередного значения функции или очередного члена последовательности, с учетом того, что эти значения известны для первого шага, называется рекуррентным соотношением. Разработка рекуррентных соотношений - это один из методов решения различных задач. В комбинаторике этот метод применяется весьма широко.

Простейшим примером рекуррентного соотношения являются формулы для вычисления числа перестановок «-элементного множества. Эти формулы имеют вид Р х = 1, Р п = Р п _ х п и могут быть получены следующим образом.

Пусть имеется п элементов /, / 2 , ..., /„, множества I. Лю

бую перестановку этих элементов можно получить так: взять некоторую перестановку элементов /, / 2 , ..., и всеми возможными способами между указанными элементами, включая начало и конец, поставить элемент / и. Ясно, что таких способов будет п. Вследствие ЭТОГО ИЗ перестановки /, / 2 , ..., / д _, будет получено п перестановок. Это означает, что перестановок из п элементов в п раз больше, чем перестановок из п -1 элементов множества I. Тем самым установлено рекуррентное соотношение Р п = Р п _ х п. Пользуясь этим соотношением, последовательно получаем Р п -пР п _ х =п(п-)Р п _ 2 - п{п - ){п -2)...2Р Х. Но Р х - 1, поскольку из одного элемента можно сделать лишь одну перестановку. Поэтому Р п = п(п -1)(« - 2)___2-1 = п. На основании изложенного

правомерна и такая запись: Р п = (п -1)!«, 1! = 1.

Теперь приведем пример рекуррентной числовой последовательности, часто называемой числами Фибоначчи, по имени итальянского математика XIII века, установившего ее как результат решения следующей задачи. Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца). Новорожденные крольчата через два месяца после рождения тоже приносят приплод. Сколько кроликов появится через год, если в его начале была одна пара кроликов?

Из условия задачи следует, что через месяц будет две пары кроликов (приплод принесет первая пара кроликов). Через два месяца - три пары, а через три месяца - пять пар, так как даст приплод еще та пара, которая появилась после первого месяца.

Обозначим через /„ количество пар кроликов по истечении п месяцев с начала года. Тогда в начале года / 0 = 1, через месяц /, = 2, через два месяца / 2 = / 0 + /, = 3, через три месяца / 3 = = / 2 + /1 =5. Поэтому в общем случае для вычисления числа кроликов в конце любого месяца получаем рекуррентное соотношение /„ = + / я _ 2 . Это соотношение дает возможность

вычислить количество пар кроликов в конце года по выражению /12 = /п + /ю П Р И условии, что / 0 = 1, /, = 2. Оно равно 377. Числа, которые получаются в результате применения приведенного рекуррентного соотношения, т.е. последовательность 1, 2, 3, 5, 8, 13, ... называются числами Фибоначчи. Примечательно, что при помощи рекуррентного соотношения, описывающего этой числовой ряд, решаются многие задачи комбинаторики. Вот одна из них.

Найти число последовательностей из нулей и единиц длиной п таких, в которых две единицы не стоят рядом. Убедимся в том, что эта задача решается при помощи рекуррентного соотношения

/я = /«-1 +/я- 2-

Возьмем любую последовательность из п +1 нулей и единиц такую, что в ней не идут две единицы подряд. Она может оканчиваться на нуль или единицу. Если последовательность оканчивается на нуль, его можно отбросить и получить последовательность длиной п, в которой две единицы не стоят рядом. Наоборот, если взять эту последовательность и приписать ей в конце нуль, то получим такую последовательность длиной п + 1, в которой две единицы не стоят рядом.

Пусть число последовательностей длиной п +1, в которых две единицы не стоят рядом и которые оканчиваются на нуль, равно g n . Возьмем теперь последовательность ДЛИНОЙ /7 + 1, в которой две единицы не стоят рядом и которая оканчивается на единицу. Так как две единицы не стоят рядом, перед последней единицей последовательности стоит нуль, т.е. последовательность оканчивается на 01. Отбрасывая эти цифры, получим последовательность длиной п - 1, в которой две единицы не стоят подряд. Число таких последовательностей g n _^. Так как каждая последовательность длиной п + 1, в которой две единицы не стоят подряд оканчивается на единицу или нуль, для общего числа таких последовательностей по правилу суммы получаем g n+ ^ - g n + g n _ x . При этом для последовательностей длиной п = 1 существует две последовательности: 0 и 1, в которых две единицы не стоят рядом, вследст-

вие чего g l - 2. Для последовательностей длиной п - 2 существует три последовательности, в которых две единицы не стоят рядом: 00, 01 и 10. Поэтому = 3. Таким образом, рекуррентное соотношение g n+l = g n + g n _ { , g^ = 2, g 2 =3 эквивалентно рекуррентному соотношению / я+1 = /„ + /, =2, / 2 = 3, описывающему ряд

Фибоначчи. Следовательно, для любого /7 = 1,2, ..., используя это соотношение, можно решить сформулированную выше задачу.

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

Общим решением рекуррентного соотношения (1) называется множество всех последовательностей, удовлетворяющих этому соотношению.

Частным решением соотношения (1) называется одна из последовательностей, удовлетворяющих этому соотношению.

Пример 1¢. Последовательность a n =a 0 +nd a n =a n - 1 +d . Это - формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a 0 .

Пример 2¢. Последовательность b n =b 0 ×q n является общим решением соотношения b n =b n - 1 ×q . Это - формула общего члена геометрической прогрессии со знаменателем q ¹0 и с начальным членом прогрессии b 0 .

Пример 3¢. Так называемая формула Бине j n =является частным решением соотношения j n =j n - 2 +j n - 1 при j 0 =j 1 =1.

Так как простые корни x 1 ,…,x k попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение.

Задача 1. Найти общий член геометрической прогрессии по формуле (4).

Решение b n =qb n - 1 имеет вид . Поэтому .

Задача 2. Найти общее решение соотношения Фибоначчи a n + 2 =a n +a n + 1 .

Решение . Характеристический многочлен рекуррентного соотношения a n + 2 =a n +a n + 1 имеет вид . Поэтому .

Приведем без доказательства следующее обобщение теоремы 1.

Теорема 2 . Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a 1 кратности , …, a k кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

Задача 3. Найти общее решение соотношения .

Решение. Характеристический многочлен имеет корень 2 кратности 3. Поэтому .

Замечание . Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).

4. Производящие функции. Формальный ряд a 0 +a 1 x +a 2 x 2 +…+a k x k +… называется производящей функцией последовательности a 0 ,a 1 ,a 2 ,…,a k ,…

Производящая функция является или сходящимся рядом, или расходящимся рядом. Два расходящихся ряда могут быть равны как функции, но быть производящимися функциями различных последовательностей. Например, ряды 1+2x +2 2 x 2 +…+2 k x k +… и 1+3x +3 2 x 2 +…+3 k x k +… определяют одну и ту же функцию (равную 1 в точке x =1, неопределенную в точках x >1), но являются производящими функциями различных последовательностей.

Свойства производящих функций последовательностей:

сумма (разность) производящих функций последовательностей a n и b n равна производящей функции сумме (разности) последовательностей a n +b n ;

произведение производящих функций последовательностей a n и b n является производящей функцией свёртки последовательностей a n и b n :

c n =a 0 b n +a 1 b n - 1 +…+a n - 1 b 1 +a n b 0 .

Пример 1. Функция является производящей для последовательности

Пример 2. Функция является производящей для последовательности 1, 1, 1, …

Рекуррентное соотношение имеет порядок k , если оно позволяет выразить f(n+k) через f(n), f(n+1), …, 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 членов заданы, то все остальные элементы определяются однозначно.

Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, при этом рано или поздно мы получим любой её член. Однако если необходимо узнать только один определенный член последовательности, то нерационально вычислять все предыдущие. В этом случае удобнее иметь формулу для вычисления n-го члена.

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

Пример . Последовательность 2, 4, 8, …, 2 n является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство . Общий член последовательности имеет вид f(n)=2 n . Значит, f(n+2)= 2 n+2, f(n+1)= 2n+1 . При любом n имеет место тождество 2 n+2 =3∙2 n+1 – 2∙2 n . Следовательно, при подстановке последовательности 2 n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2 n является решением указанного соотношения.

Решение рекуррентного соотношения k-го порядка называется общим , если оно зависит от k произвольных постоянных α 1 , α 2 , … α k и путем подбора этих постоянных можно получить любое решение данного соотношения.

Пример . Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2 n + β3 n .

1. Сначала докажем, что последовательность f(n)=α 2 n + β3 n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.

f(n)= α 2 n + β 3 n , значит, f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , тогда

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f(n+2).

Рекуррентное соотношение выполняется, следовательно, α 2 n + β 3 n является решением данного рекуррентного соотношения.

2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2 n + β 3 n . Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.

Таким образом, f(n)= α 2 n + β 3 n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).

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

Для решения рекуррентных соотношений общих правил нет, но существует часто встречающийся класс рекуррентных соотношений, для которых известен алгоритм их решения. Это – линейные рекуррентные соотношения с постоянными коэффициентами, т.е. соотношения вида:

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, аналогично f(4)=c 3 ∙a и так далее, заметим, что f(n)=c n -1 ∙f(1).

Докажем, что последовательность c n -1 ∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=c n -1 ∙f(1), значит, f(n+1)=c n f(1). Подставляя это выражение в соотношение, получим тождество c n f(1)=с∙ c n -1 ∙f(1).

Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка , то есть соотношения вида

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

Заметим, что все рассуждения сохраняются и для соотношений более высокого порядка.

Свойства решений :

1) Если последовательность x n является решением (*), то и последовательность a∙x n тоже является решением.

Доказательство.

x n является решением (*), следовательно, выполняется тождество x n +2 =C 1 x n +1 +C 2 x n . Домножим обе части равенства на a. Получим a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Это означает, что ax n является решением (*).

2) Если последовательности x n и y n являются решениями (*), то и последовательность x n +y n тоже является решением.

Доказательство.

x n и y n являются решениями, следовательно, выполняются следующие тождества:

x n +2 =C 1 x n +1 +C 2 x n .

y n +2 =C 1 y n +1 +C 2 y n .

Выполним почленное сложение двух равенств:

x n +2 +y n +2 =С 1 ∙x n +1 +С 2 ∙x n + С 1 ∙y n +1 +С 2 ∙y n = С 1 ∙(x n +1 + y n +1)+С 2 ∙(x n +y n). Это означает, что x n +y n является решением (*).

3) Если r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , то последовательность (r 1) n является решением для соотношения (*).

r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , значит, (r 1) 2 =C 1 r 1 +C 2 . Помножим обе части равенства на (r 1) n . Получим

r 1 2 r 1 n =(С 1 r 1 +С 2) r n .

r 1 n +2 =С 1 r 1 n +1 +С 2 r 1 n .

Это означает, что последовательность (r 1) n является решением (*).

Из этих свойств вытекает способ решения линейных рекуррентных соотношений с постоянными коэффициентами второго порядка:

1. Составим характеристическое (квадратное) уравнение r 2 =С 1 r+С 2 . Найдём его корни r 1, r 2. Если корни различны, то общее решение имеет вид f(n)= ar 1 n +βr 2 n .

2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений

имеет решение при любых а и b. Этими решениями являются

Задача. Найдем формулу для общего члена последовательности Фибоначчи.

Решение. Характеристическое уравнение имеет вид х 2 =х+1 или х 2 -х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= . Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:

.

Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.