Дискретная математика / ДМ_Комбинаторика

Пример решения задания 6.3.

Найти частное решение рекуррентного соотношения 4-го порядка f n 4 6 f n 2 8 f n 1 3 f n ,

удовлетворяющее начальным условиям f 0 0, f 1 6, f 2 4, f 3 34 .

Решение. Характеристическое уравнения для данного соотношения имеет вид:

x4 6 x2 8 x 3 0 .

Подстановкой убеждаемся, что x1 1 – корень характеристического уравнения. Понизим степень уравнения, поделив характеристический многочлен на x 1 по схеме Горнера:

1

0

– 6

– 8

– 3

– 1

1

– 1

– 5

– 3

0

В результате деления приходим к уравнению третьей степени x3 x2 5 x 3 0 , для ко-

торого x2 1

также является корнем. Разделим левую часть уравнения на x 1:

1

– 1

– 5

– 3

– 1

1

– 2

– 3

0

31

Получим следующее уравнение x2 2 x 3 0 , корни которого x3 1, x4 3 . Учитывая

кратность корня x 1 характеристического уравнения, запишем общее решение рекуррентного соотношения:

f n 1 n A Bn Cn2 D 3n .

Учтём начальные условия и получим систему линейных алгебраических уравнений:

A D 34,

A B C 3D 6,

A 2B 4C 9D 4,

A 3B 9C 27D 34.

Решив систему, найдем: A 1, B 2, C 0, D 1. Подставим найденные значения констант в формулу общего решения, получим:

f n 1 n 1 2n 0 n2 1 3n .

Ответ: f n 1 n 1 2n 3n .

32