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

Наша ближайшая цель – определить, какой вид имеет производящая функция произвольной линейной рекуррентной последовательности.

Рассмотрим в качестве примера производящую функцию последовательности чисел Фибоначчи:

F(z) = F0 + F1z + F2z2 + … . (4)

Умножим F(z) на z и на z2:

zF(z) = F0z + F1z2 + F2z3 + … ;

z2F(z) = F0z2 + F1z3 + F2z2 + … .

Так как F2 = F1 + F0; F3 = F2 + F1;… , то

zF(z) + z2F(z) = F0z + F2z2 + F3z3 + … .

Учитывая, что F0 = 0 и F1 =1, получаем:

z + zF(z) + z2F(z) = F(z).

Отсюда получается компактная формула:

F(z) = z . (5)

1 − z − z 2

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

Фибоначчи. Начнем с того, что представим дробь из (5) в виде

Тогда

z

1 − z − z 2

A

= A +

1 − бz

n

B

1 − вz

B

. (6)

n

1 − бz

A ∑ (бz)

n ≥ 0

;

1 − вz

 B ∑ (вz) ,

n≥ 0

и, значит,

z

= A ∑(бz)n + B ∑(вz)n = ∑( Aб n  Bв n ) z n .

1 − z − z 2

n≥ 0

n≥ 0

n≥0

Таким образом,

Fn = An + Bn.

Чтобы найти неизвестные коэффициенты A, B,  и , приведем дроби из (6) к общему знаменателю и приравняем коэффициенты при одинаковых степенях z. Получаются следующие уравнения:

 +  = 1;  = –1; A + B = 0; A +B = –1.

Решая полученную систему, находим:

б  1 

5 ; в  1 −

2

5 ; A =

1 ; B = − 1 .

5 5

Окончательно получаем:

1 1 5 n

5  

    

Fn  



Пусть теперь

 − 

2  . (7)



u0, u1, u2,… – (8) произвольная рекуррентная последовательность, удовлетворяющая соотношению

un+r = a1un+r–1 + a2un+r–2 +…+ arun , (9)

и

f(z) = u0 + u1z + u2z2 +… –

ее производящая функция. Рассмотрим произведение f(z) на

многочлен

h(z) = 1 – a1z – a2z2 –…– arzr .

Коэффициент при zn+r равен

un+r – a1un+r–1 – a2un+r–2 –…– arun ,

и, значит, обращается в ноль в силу (9). Таким образом, в произведении h(z)f(z) все коэффициенты при степенях z, больших или равных r, обращаются в ноль, т. е. g(z) = h(z)f(z) – это многочлен степени не выше чем r – 1. Производящая функция последовательности (8) оказывается равной дробно-

рациональной функции

f ( z) 

g(z) .

h(z)

Примеры.1. Для геометрической прогрессии со знаменателем q имеем

f(z) = u0 + u0qz + u0qz2 +…; h(z) = 1 – qz; h(z)f(z) = u0 ,

откуда получается хорошо известная формула:

f ( z) 

u0 .

1− qz

2. Пусть теперь u0, u1, u2,… – арифметическая прогрессия.

Так как un+2 = 2un+1 – un , то

h(z) = 1 – 2z + z2

и

Следовательно,

h(z)f(z) = u0 + (u1 – 2u0)z2.

f ( z)  u0  (u1 − 2u0 )z . (10) (1 − z)2

Рассмотрим, в частности, последовательность положительных целых чисел 1, 2, 3, … . Запишем ее производящую функцию:

f(z) = 1 + 2z + 3z2 + … . (11)

По формуле (10) получаем:

f ( z) 

(1−z)2

. (12)

К тому же результату можно придти по-другому. Ряд (11)

получается как производная ряда

z + z2 + z3+ … ,

сумма которого (как сумма геометрической прогрессии) равна

z

1− z

. (13)

Дифференцируя (13), получаем (12).

Наряду с многочленом h(z) рассмотрим многочлен

k(z) = zr – a1zr–1 – a2zr–2 –…– ar,

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

Многочлены h(z) и k(z) связаны простым соотношением:

h(z) = zrk(1/z).

Пусть 1, 2, …, s – корни характеристического многочлена

(возможно, комплексные) с кратностями p1, p2, …, ps. Тогда

k ( z)  ( z − б1

и, соответственно,

) p1 ( z − б 2

) p2 K( z − б s

) ps ,

h(z) (1−б1

z)p1 (1− б2

z)p2 K(1− бs

z) ps .

Рациональная функция

f ( z) 

g ( z)

h(z)

может быть представлена в

виде суммы простых дробей вида

в

(1− бz) p

, (14)

где  = i – один из корней характеристического многочлена, p

лежит в промежутке от 1 до pi, а  – некоторое число.

Разлагая (14) по формуле бинома, получаем:

в − p 

n n n

(1 бz) p

 ∑в

(−1) б z .

n

−

Относительно n выражение

n ≥ 0  

− p  n n n

n n p −1

 (−1)

 n 

 (−1)

C p  n −1 ⋅(−1)

 C p  n −1  C p  n −1

является многочленом степени не выше p – 1 и, тем более, не выше pi – 1. Следовательно, сумма всех дробей вида (14),

относящихся к одному и тому же корню  = i, может быть

представлена в виде

∑P (n)бnzn , причем степень многочлена

i i

n≥0

Pi(n) не превышает pi – 1. Суммируя по всем i = 1, 2, …, s,

получаем:

 s n  n

f ( z) 

∑ ∑ Pi (n)i z .

n ≥ 0i 1 

Сравнивая полученное выражение с

f(z) = u0 + u1z + u2z2 +… ,

приходим к заключению, что

s

un ∑

i 1

. (15)

Пример.Рассмотрим последовательность 6, 0, 12, … ,

удовлетворяющую рекуррентному соотношению

un+3 = 3un+1 + 2un.

Многочлен

k(z) = z3 –3z – 2

является характеристическим для этой последовательности.

Раскладывая его на множители получаем:

k(z) = (z + 1)2(z – 2).

Следовательно, члены рассматриваемой последовательности имеют вид

un = P(n)⋅(–1)n + Q⋅2n ,

где P(n) – многочлен степени не выше первой, а Q – степени не выше нулевой (т. е. ноль или некоторое число).

Будем искать un в виде

un = (An + B)⋅(–1)n + Q⋅2n .

Поскольку u0 = 6, u1 = 0, u2 = 12, получаем следующие уравнения относительно A, B и Q:

B + Q = 6; –(A + B) + 2Q = 0; 2A + B + 4Q = 12.

Решая систему, находим:

Следовательно,

A = 0; B = 4; Q = 2.

un = (–1)n⋅4 + 2n+1.

Пример.Используя (15), найдем формулу для суммы квадратов первых n натуральных чисел.

Суммы квадратов связаны рекуррентным соотношением

sn+4 = 4sn+3 – 6sn+2 + 4sn+1 – sn. Характеристический многочлен последовательности сумм квадратов

k(z) = z4 – 4z3 + 6z2 – 4z +1 = (z – 1)4

имеет единственный корень 1 кратности четыре.

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

sn = An3 + Bn2 + Cn +D.

Так как

то

s0 = 0, s1 = 1, s2 = 5, s3 = 14,

D = 0; A + B + C = 1;

8A + 4B + 2C = 5; 27A + 9B + 3C = 14.

Вычисляем определитель системы уравнений, содержащих неизвестные A, B, C, и определители, соответствующие переменным:

 1



∆   8

1 1 



4 2   −12 ;

 1



1 1 



14 9 

 1



∆B   8

1 1 



5 2   −6 ; ∆С

 1



1 1 



 27

9 14 

Находим: A = 1/3; B = 1/2; C = 1/6. Следовательно,

s  1n3  1n2  1n  n(n  1)(2n  1) .

n 3 2 6 6