Курсовая работа по «Методам решений рекуррентных соотношений»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ПЕРМСКИЙ ГУМАНИТАРНО-ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра высшей математики

 

 

 

Курсовая работа по дисциплине

МЕТОДЫ РЕШЕНИЯ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ

 

                              

 

 

 

 

 

 

 

 

Пермь

2014

Введение

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

Здесь можно представить очень краткую (на 2-3 предложения) историческую справку и характеристику современного состояния исследуемого вопроса.

Методы исследования. В работе использованы методы анализа

теоретической информации, дискретной математики, построения и анализа

алгоритмов, теории автоматов

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

Если последовательность чисел или функций конечна, то для нахождения значений функций (например, суммы, произведения или n-ого члена) используется арифметический цикл, т.е. цикл, в котором заранее известно число повторений. Трудность при решении таких задач представляет нахождение самой рекуррентной формулы. Я предлагаю ученикам общий подход к получению рекуррентной формулы, опираясь на метод математической индукции.

Цель исследования – изучение методов решения некоторых рекуррентных соотношений.

В связи с поставленной целью необходимо решить следующие задачи:

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

Объектом курсового исследования являются рекуррентные соотношения.

Предмет исследования – методы их решения.

 
 

1.​ Основные понятия

1.1.​ Примеры задач, приводящих к рекуррентным соотношениям

Рассмотрим некоторые задачи, приводящие к рекуррентным соотношениям.

Одной из них является - Числа Фибоначчи. Итальянский математик Фибоначчи привел следующую задачу: пара кроликов раз в месяц дает приплод из двух крольчат (самки и самца), причем навоженные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появиться через год, если в начале года была одна пара кроликов?

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получиться 3 пары. А еще через месяц приплод дадут и исходная пара, и пара кроликов, проявившая два месяца тому назад. Поэтому всегда будет 5 пар кроликов.

Обозначим через f(n)количество пар кроликов по истечении nмесяцев сначала ода. Мы видим что через n+1 месяцев будет f(n) еще сколько новорожденных пар кроликов, сколько было в конце месяца n-1, то есть еще f(n-1)пар кроликов. Иными словами, имеет место рекуррентное соотношение

f(n+1)=f(n)+f(n-1)

Так как по условию f(0)=1 иf(1)=2, то последовательность находим f(2)=3, f(4)=8 и т.д. Числа f(n) называется числами Фибоначчи.

Задача о Ханойской башне. Рассмотрим головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков (рис. 1)

 

 

 

Рис.1. Ханойская башня

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

Пусть f(n)-минимальное число перекладываний nдисков с одного колышка на другой по правилу Люка. Очевидно, что f(0)=0,f(1)=1,а f(2)=3.В случае трех дисков, два верхних диска переносятся на один из колышков, затем переносится третий диск на него помещаются два других. Таким образом, общее правило перемещений заключается в следующем. Сначала перемещается n-1 меньших дисков на один из колышков-этоf(n-1) перекладываний. Затем перекладывают самый большой диск-это одно перекладывание, и, наконец,n-1меньших дисков переносятся на самый большой диск-это еще f(n-1)перекладываний. Получается, что n(n дисков можно за 2f(n-1)+1 перекладываний.

Вместе с тривиальным решением при n=0,получаем два равенства:

f (0) = 0

f (n)=2 f (n -1) +1 при п> 0

Совокупность равенств такого типа называется рекуррентностью (также в литературе встречается термин возвратное соотношение или рекурсивная зависимость) Полностью задать рекуррентное соотношение-значит задать начальные условия и зависимость общего члена от предыдущих.

Еще одна задача-задача о разрезании пиццы. Задача имеет геометрический характер: сколько кусков пиццы можно получить, делая n прямоугольных разрезов ножом? Или каково максимальное число f(n)областей, на которые плоскость делится nпрямыми? Впервые эта задача была решена в 1826 г. швейцарским математиком Якобом Штейнером.

Плоскость без прямых(n=0)-это одна плоскость-f(0)=1.

 

Рис.2                                   Рис.3                                  Рис.4

Плоскость с одной прямой (n=1)-две области-f(1)=2 (рис.2).

Плоскость с двумя прямыми (n=2)-четыре области-f(2)=4 (рис.3).

Когда добавляется третья прямая (рис.4), то она может рассекать самое большое три старые области вне зависимости от того, как расположены первые две прямые. Таким образом, f(3)=4+3=7-самое большое что можно сделать. Очередная k-я прямая(приn) увеличивает число областей на k,при этом она рассекает k предыдущих областей, пересекая прежние прямые в k-1различных точках. Две прямые могут пересекаться не более чем в одной точке. Поэтому n-я прямая может пересекать n-1 предыдущих прямых не более чем в n-1 различных точках. Следовательно, должно выполняться неравенство kn. Получаем верхнюю границу

f (n) £ f (n -1) + n при n >0

Равенство достигается, если повести n-ю прямую так, чтобы она не была параллельна никакой другой прямой (т.е. пересекала бы каждую из них), и чтобы она не проходила ни через одну из имеющихся точек пересечения (т.е. пересекает каждую из прямых в различных точках).

Учитывая тривиальное решение при n=0, получаем полное задание рекуррентного соотношения

f(0) = 1

f(n) = f (n -1) + n приn > 0

 

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

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

Рис.5.Случай для 10 человек

 

В результате номер уцелевшего J(10)=5.

Обобщим случай для любого четного количества человек. Пусть первоначально имеется 2nлюдей. После первого перехода круга остаются нечетные номера, и следующий переход начинается с номера 3, причем, количество людей в круге становиться в 2 раза меньше. Это равносильно тому, что в круге присутствуют nчеловек, с той лишь разницей, что номер каждого присутствующего удваивается и уменьшается на 1. Следовательно, для четного случая получаем равенство

J(2n)=2J(n)-1,при п≥ 1

В нечетном случае человек с номером 1исключаеться сразу после номера 2n, и получаем ситуацию с n людьми, но в этот раз номера оставшихся удваиваются и увеличиваются на 1. Таким образом, получаем равенство для нечетного количества человек

J(2n+1)=2J(n)+1,при п≥ 1

Объединяя два равенства и учитывая начальное условие J(1)=1, составляем рекуррентное соотношение

J(1)=1

J(2n)=2J(n)-1, при п≥ 1                   (3)

J(2n+1)=2J(n)+1, при п≥ 1

Составим таблицу для разных значений n (количество человек, стоящих в круге)

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
J(n)	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1	3	5	7	9

Проверим: J (20) = 2J (10) -1= 2 × 5 -1= 9.

Для того, чтобы решить соотношение (3) сгруппируем значения nпо степеням 2(таблица ниже), то в каждой группе J(п) всегда будет начинаться с 1, а затем увеличиваться на 2.

Степень 2
n	1	2     3	4 5 6 7	8 9 10 11 12 13 14 15	16 17 18 19 20 21 22 ...
J(n)	1	1     3	1 3 5 7	1 3 5 7 9 11 13 15	1 3 5 7 9 11 13 ...

 

Таким образом, записывая количество человек в виде n=2m+1, где 2m- наибольшая степень 2, не превосходящая n, а 1-остаток. То решение задач будет выглядеть следующим образом

J (2m + l) = 2l +1, m ³ 0, 0 £ l < 2m (38)

1.2.​ Понятие рекуррентного соотношения

Рекуррентные соотношения (от лат. recur-rens, род, падеж recurrentis - возвращающийся) - однотипные формулы, которые связывают между собой идущие друг за другом элементы некоторой последовательности (это может быть последовательность чисел, функций и т. д.). В зависимости от природы объектов, связанных рекуррентные соотношения, эти соотношения могут быть алгебраическими, функциональными, дифференциальными, интегральными и т. п.

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

Пример:

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

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

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

Рекуррентное соотношение имеет порядок. Рекуррентное соотношение имеет порядок k, если оно позволяет выразитьf(n+k) черезf(n), f(n+1),.…,f(n+k-1).

Пример:

f(n+2)=f(n) f(n+1)-3(n+1)+1- рекуррентное соотношение второго порядка.

f(n+3)=6f(n) f(n+2)+f(n+1)- рекуррентное соотношение третьего порядка.

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

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

Например, последовательность

,…

явлеться одним из решений рекуррентного соотношения

f(n+2)=3f(n+1)-2f(n).

В самом деле, общий член этой последовательности имеет вид f(n)=

Значит . Но при любом nимеет место тождество . Поэтому являеться решением указанного соотношения.

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

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

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

Пример:

Для соотношения   (5) общим решением будет  
(6)

В самом деле, легко проверить, что последовательность (6) обращает (5) в тождество. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде (6). Но любое решение соотношения (5) однозначно определяется значениями f(1) и f(2). Поэтому нам надо доказать, что для любых чисел a и b найдутся такие значения  и , что и

Но легко видеть, что при любых значениях   и   система уравнений

 

имеет решение. Поэтому (6) действительно является общим решением соотношения (5).

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

Пример:

Последовательность явлется решением рекуррентного соотношения так как имеет место тождество

1.3. Виды рекуррентных соотношений

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

f(n+k)= 
где a1, a2, …, an – некоторые числа Такие соотношения называют однороднымилинейными рекуррентными соотношениями с постоянными коэффициентам n.

Неоднородное линейное рекуррентное соотношение имеет вид

f(n+k)=  (8)

где величина b(n) в общем случае является функцией от n. Общее решение соотношения (8) представляет собой сумму частного решения неоднородного уравнения (8) (то есть любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (8).

Общих способов определения частного решения нет, однако для некоторых значений b(n) существуют стандартные приемы определения f(n) .

Для неоднородного линейного рекуррентного соотношения вида:

F(n+2)+pf(n+1)+qf(n)=n+(9)

где α, β, p, q – данные числа, справедливы следующие утверждения:

1) если х0 =1 не является корнем многочлена х2 +px+q, то частным решением рекуррентного соотношения (9) является последовательность f=an+b;

2) если х0 =1 является простым корнем многочлена х2 +px+q, частное решение рекуррентного соотношения (9) может быть найдено в виде f=n(аn+b);

3) если х0 =1 является кратным корнем многочлена х2 +px+q, частное решение рекуррентного соотношения (9) может быть найдено в виде f=n2 (аn+b).

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

1.1. Определение. Пусть () — некоторая числовая последовательность, и пусть

f(z) = …

есть формальный степенной ряд для этой последовательности, понимаемый как элемент кольцаC[[z]] . Производной ряда f(z) называется формальный степенной ряд вида

 

Иными словами, производной числовой последовательности () в кольце с операцией  умножения 
называется числовая последовательность:

 

1.2. Определение. Пусть

 

есть формальный степенной ряд для числовой последовательности (). Производнойэтого ряда называется формальный степенной ряд вида

 

Иными словами, “экспоненциальной” производной числовой последовательности () является сдвинутая на одну позицию влево числовая последовательность ().

1.3. Для операции  взятия производной в кольцах  C[[z]] и [[z]] формальных степенных рядов можно выводить свойства, аналогичные привычным нам свойствам производной из классического анализа. При этом вывод этих свойств зачастую оказывается даже более простым по сравнению с аналогичным выводом в курсе математического анализа.

 

 

 

2. Основные методы решения рекуррентных соотношений

 

1. Решение линейных однородных рекуррентных соотношений с постоянными коэффициентами

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

PC вида

f (n + k) = d1f (n + k −1) + d2f (n + k − 2) +...+ dkf (n),          (2.1)

где d1, d 2, ..., dk – некоторые действительные (возможно, комплексные) числа, называются линейными однородными PC с постоянными коэффициентами.

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

Примерами возвратных последовательностей могут быть прогрессии:

1) геометрическая – a(0) = a, a(1) = aq, a(2) = aq2, ..., являющаяся решением PC f (n) = qf (n −1) при n ≥1 и f (0) = a;

2) арифметическая – a(0) = a, a(1) = a + d, a(2) = a + 2d, ..., являющаяся решением PCf (n)= 2f (n −1)− f (n − 2) при n ≥ 2 и f (0) = a, f (1) = a + d.

Теорема 2.1 (о сумме двух решений). Если a(n) и b(n) являются частными решениями PC (2.1), то для любых действительных чисел m и r последовательность m⋅ a(n) + r ⋅b(n) также есть решение PC (2.1).

Доказательство. Пусть последовательности a(n) и b(n) есть частные решения PC (4.7), т. е.

a(n + k) − d1a(n + k −1) − d2a(n + k − 2) −...− dka(n) = 0

иb(n + k) − d1b(n + k −1) − d2b(n + k − 2) −...− dkb(n) = 0.

Тогда, умножив эти равенства на числа m и r соответственно и сложив их, получаем

m× (a(n + k) – d1a(n + k – 1) – d2a(n + k – 2) – … – dka(n)) + r × (b(n + k) –

-d1b(n + k – 1) – d2b(n + k – 2) - dkb(n)) = m × 0 + r × 0 = 0

т. е. последовательность m⋅a(n) + r⋅b(n) также является решением PC (2.1). Доказательство завершено.

Для PC (2.1) составим алгебраическое уравнение

p(x) ºxk– d1xk-1 – d2xk-2 – … – dk-1x – dk = 0,                           (2.2)

которое называется его характеристическим уравнением.

Теорема 2.2 (о корне характеристического уравнения). Пусть r есть корень характеристического уравнения (2.2).

1. Тогда функция rn является решением PC (2.2).

2. Если же r есть корень  кратности d (d ≥ 2), то каждая из  функций nrn, n2rn, ... , nd −1rn также является решением PC (2.1).

Доказательство. Пусть выполняются условия этой теоремы. Сначала рассмотрим случай, когда r есть корень кратности 1 уравнения (2.2). Тогда выполняется равенство

rk– d1rk-1 – d2rk-2 – … – dk-1r – dk = 0,            

или

rk= d1rk-1 + d2rk-2 + … + dk-1r + dk.           

Умножая последнее равенство на rn, получим равенство

rk+n= d1rn+k-1 + d2rn+k-2 + … + dk-1rn+1 + dkrn,

что означает: функция rn есть решение PC (2.1).

Теперь пусть r есть корень уравнения (2.2) и его кратность равна d (d ≥ 2) и для простоты выкладок полагаем, что d = 2. В этом случае требуется доказать, что и функция nrn также есть решение PC (2.1).

Построим два выражения:

rk − d1rk-1 − d2rk-2 − … − dk-1r − dkrn − dk

и

krk-1 − d1(k-1)rk-2 − d2(k-2)rk-3 − … − dk-1,

первое из которых есть значение полинома p(x) в точке r, т. е. p(r), а второе – значение первой производной по x этого же полинома в точке r, т. е. p′(r). Так как r есть корень полинома p(x), то p(r) = 0 и p′(r) = 0, потому что r есть корень кратности 2. Теперь построим выражение nrn p(r) + rn−1p′(r), которое эквивалентно преобразуется в равенство

(n + k) rk+n = d1(n + k-1)rn+k-1 + … + dknrn.

Но это равенство означает, что nrn действительно есть решение PC (2.1). Доказательство завершено.

Из теоремы 2.2 следует, что решений линейного однородного PC с постоянными коэффициентами столько, сколько корней имеет его характеристическое уравнение с учетом их кратности, и это число равно его порядку. К тому же, все решения линейно независимы, так как имеют различные порядки роста в бесконечности, и таковыми должны быть согласно определению общего решения PC. А согласно теореме 2.1 каждое решение рассматриваемого PC должно быть выражено в виде линейных комбинаций частных решений вида по теореме 2.2. Следовательно, верно.

Следствие 2.1. Пусть линейное однородное PC с постоянными коэффициентами (2.1) такое, что его характеристическое уравнение имеет корни ri (1≤ i ≤ s) кратности di соответственно. Тогда общее решение a(n) такого линейного однородного PC с постоянными коэффициентами представляется в виде

 

Использование начальных значений f (0) = a0, f (1) = a1, ..., f (k −1) = ak−1 PC (2.1) приводит к системе из k линейных уравнений

 

из которой коэффициенты cij (1≤ i ≤ s, 1≤ j ≤ di) решения a(n) находятся однозначно.

Пример 2.1. Найти решение линейного однородного PC с постоянными коэффициентами f (n + 2) = 5 f (n +1) − 6 f (n), удовлетворяющее начальным значениям f (0) = 5, f (1) =12.

Характеристическое уравнение этого PC x2 − 5x + 6 = 0 имеет корни 2 и 3, кратность каждого из которых есть 1. Следовательно, общее решение данного PC есть c12n + c23n. Используя начальные значения, составляем систему уравнений

 

решение которой – c1 = 3, c2 = 2. Значит, требуемое решение есть последовательность 3⋅ 2n + 2⋅3n , n ≥ 0.

Пример 2.2. Найти решение линейного однородного PC

f (n + 3) = 9 f (n + 2) − 24 f (n +1) + 20 f (n),

удовлетворяющее начальным значениям f (0)=6, f (1)=30, f (2)=132.

Характеристическое уравнение этого PC x3 − 9x2 + 24x − 20 = 0 имеет корни 2 и 5, причем кратность первого равна 2, а второго – 1.

Тогда общее решение данного PC есть (c1 + c2n)2n + c35n.

Используя начальные значения, составляем систему уравнений

 

корни которой есть c1 = 2, c2 = 3, c3 = 4. Следовательно, требуемым решением является (2 + 3n)2n + 4⋅5n , n ≥ 0.

Пример 2.3. Найдем решение линейного однородного PC

f (n + 2) = f (n +1) + f (n),

удовлетворяющее начальным значениям f (0) = f (1) =1, которое задает последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, … .

Его характеристическое уравнение x2 − x −1= 0 имеет корни

.

Значит, общее решение этого PC есть c1r1n + c2r2n. Используя начальные значения, составляем систему уравнений

 

корни которой

.

Следовательно, требуемое решение есть

 

2.2. Решение линейных  неоднородных рекуррентных соотношений  с постоянными коэффициентами

Другим классом PC, для специальных видов которых имеется общая теория их решения, являются линейные (неоднородные) PC с постоянными коэффициентами.

PC вида

f (n + k) = d1f (n + k −1) +...+ dk f (n) + v(n),         (2.3)

где d1, ..., dk– некоторые числа, а v(n) – функция от n, не равная 0, называются линейными PC с постоянными коэффициентами. Примерами таких PC являются

g(n) = g(n −1) + g(n − 2) +1

и

f (n +1) = f (n) + n +1(2.4)

с заданными начальными значениями g(0) и g(1), f (0).

Теорема 2.3 (об общем решении линейного PC с постоянными коэффициентами). Общее решение рекуррентного соотношения(2.3) может быть представлено в виде суммы общего решения линейного однородного рекуррентного соотношения (2.1) и какого-либо решения рекуррентного соотношения (2.3).

Доказательство. Пусть b(c1, ...,ck,n) есть общее решение линейного однородного PC (2.1), a d(n) – одно из решений PC (2.3).

Докажем, что последовательность b(c1, ...,ck,n) + d(n) является общим решением PC (2.3). Имеем

(b(c1, ...,ck,n + k) + d(n + k)) −

         −d1(b(c1, ...,ck,n + k −1) + d(n + k −1)) −...−

−dk(b(c1, ..., ck,n) + d(n)) − v(n) =

= (b(c1, ..., ck,n + k) − d1b(c1, ..., ck,n + k −1) −...−

−dkb(c1, ...,ck,n)) + (d(n + k) − d1d(n + k −1) −

−...− dkd(n) − v(n)) = 0 + 0 = 0,

т. е. указанная последовательность действительно есть решение PC (2.3).

Осталось доказать, что если a(n) есть решение PC (2.3), то можно так подобрать параметры c1′, ..., ck′ , что при всех n будет выполняться равенство a(n) = b(c1′, ...,ck′ ,n) + d(n). Согласно тому, что a(n) и d(n) являются решениями PC (2.3), имеем

a(n + k) = d1a(n + k −1) +...+ dka(n) + v(n)

и

d(n + k) = d1d(n + k −1) +...+ dkd(n) + v(n),

откуда

a(n + k) − d(n + k) = d1(a(n + k −1) − d(n + k −1)) +...+ dk(a(n) − d(n)).

Следовательно, последовательность a(n) − d(n) есть решение линейного однородного PC (2.3). Значит, можно так подобрать параметры c1′, ...,ck′ , что при всех n будет выполняться равенство