Дискретная математика 3 (стр. 3 из 10)
В(х)=
А(х). Пусть последовательность {bk} определяется через {ak} следующим образом: bk=ak+i для k=0, 1, 2, …, тогда, В(х)=[A(x)-
]x-i. Действительно,В(х)=
. Пусть последовательность {bk} определяется через {ak} следующим образом: bk=
для k=0, 1, 2, …. Тогда, В(х)= 
. Действительно,В(х)=
=а0+(а0+а1)х+(а0+а1+а2)х2+(а0+а1+а2+а3)х3+…+(а0+а1+…+аk)хk+…= =a0(1+x+x2+x3+…)+a1x(1+x+x2+x3+…)+ a2x2(1+x+x2+x3+…)+…= =(a0+a1x+a2x2+…)(1+x+x2+x3+…)=
=
A(x) 
= .§6. Дополнительные частичные суммы.
Пусть последовательность {bk} определяется через {ak} следующим образом: bk=
для k=0, 1, 2, …. Тогда, В(х)= 
. Действительно,В(х)=
=а0+а1+а2+…+а1х+а2х+а3х+…+а2х2+а3х2+а4х2+…= =a0+a1(1+x)+a2(1+x+x2)+а3(1+x+x2+x3)+…= 
. I. Пусть последовательность {bk} определяется через {ak} следующим образом bk=k×ak. Тогда В(х)=хА¢(х). Действительно, А(х)=
и А¢(х)= 
или хА¢(х)= 
II. Пусть последовательность {bk} определяется через {ak} следующим образом bk=
. Тогда В(х)= 
.Так как А(х)=
, то 
. Пусть последовательность {сk} определяется через {ak} и {bk} следующим образом: ck=
, k=0, 1, …. Тогда С(х)=А(х)×В(х). Действительно: A(x)= ,B(x)= 
.C(x)=
.§9. Линейные рекуррентные соотношения.
Рассмотрим последовательность {un}, n=0,1,2…. Будем говорить, что задано однородное линейное рекуррентное соотношение с постоянными коэффициентами порядка r, если для членов последовательности {un} выполняется равенство:
un+r=С1un+r-1+С2un+r-2+…+Сrun, (1)
где Сi, i=
– постоянные величины. Выражение (1) позволяет вычислить очередной член последовательности по предыдущим r членам. Ясно, что, задав начальные значения u0, u1, …, ur-1, можно последовательно определить все члены последовательности.Рассмотрим общий метод решения рекуррентного соотношения (1), то есть поиска un, как функции от n. для решения задачи достаточно найти производящую функцию
U(x)=
(2)последовательности {un}. Введем обозначение:
К(х)=1-С1х-С2х2-…-Сrxr
и рассмотрим произведение U(x)K(x)=C(x), deg C(x)£r-1, так как коэффициенты при xn+r, n=0,1,2… в произведении U(x)K(x) с учетом (1), равны:
un+r-(С1un+r-1+С2un+r-2+...+Сrun)=0.
Характеристическим полиномом соотношения (1) называется многочлен
F(x)=xr-С1xr-1-С2xr-2-…-Сr-1x-Сr(3)
Выполним разложение F(x) на линейные множители:
F(x)=(x-α1)
(x-α2) 
…(x-αr) 
, где e1+e2+…+er=r.Сравнивая К(х) и F(x) можно записать: К(х)=xr⋅F
. ТогдаК(х)=
==(1-α1х)
(1-α2х) …(1-αrх) , e1+e2+…+er=r.Данное разложение на множители используется для представления выражения U(x)=
в виде суммы простых дробей:U(x)=
= 
(4)Таким образом, U(x) является суммой функций вида
.Тогда выражение (4) примет вид:
U(x)=
= 
(5)Данное разложение является производящей функцией U(x)=
последовательности {un}. Для определения un необходимо найти коэффициент при хn в разложении (5).Пример. Найти члены последовательности {un}, удовлетворяющие рекуррентному соотношению un+2=5un+1-6un, если u0=u1=1.
Решение. Начальные условия: r=2, C1=5, C2=-6.
K(x)=1-5x+6x2
K(x)⋅U(x)=С(x), где U(x)=
С(х)=(1-5x+6x2)(u0+u1x+u2x2+…)=
=u0+u1x+u2x2+…-5u0x-5u1x2-5u2x3-…+6u0x2+6u1x3+6u2x4+…=
=u0+(u1-5u0)x+(u2-5u1+6u0)x2+(u3-5u2+6u1)x3+…
Но u2=5u1-6u0, u3=5u2-6u1 и так далее. Следовательно,
С(х)=u0+(u1-5u0)x=1-4x.
Характеристическим полиномом будет F(x)=x2-5x+6=(x-2)(x-3).
Отсюда следует, что U(x)=
= 
.С помощью неопределенных коэффициентов разложим последнюю дробь в сумму дробей:
= 
= 
= 
.