1.2    Рекуррентные соотношения и производящие функции

Пусть .Р - некоторое поле и {щ, мі,...} - последовательность чисел из .Р. Скажем, что эта последовательность является рекуррентной порядка г, если существуют числа с/1..... а,- Є У такие, что

иг = а\иг^\ + и->и,—-> + • • • + и,- ■ щ,

11,-1 = (і\ (іг + а--уиг-\ + • • • + а,- ■

где п = 0,1,2,.... Для рекуррентной последовательности {ип} многочлен /(х) = хг — а\хг^1 — ■ ■ ■ — аг = (х — а\)ел ... (ж — а8)е% где ^    = г,

а\,..., а8 £ Р, называется характеристическим (.Р - алгебраическое замы­кание поля Р: например, С = С. Й, = С). Рассмотрим, далее, множество

00

Р((х)) =      угх%'-> у% ^      всех формальных степенных рядов от переменной

$=0

х с коэффициентами из поля Р. Определим на этом множестве следующие

операции:

00

г=0 г=0 г=0

00 00 00

i=0 %=д i=0

'I

где (I; = ^ •*'/''<';-/• Легко видеть, что (Р ((:>:)). +,.) является ассоциативным и

коммутативным кольцом с единицей 1 = 1 + 0-ж + 0-ж2+-- - , не содержащим делителей нуля (т.е. если а-/? = 0, где а, /3 £ Р{{:/;)). либо а = 0, либо /? = 0).

00

При этом ряд *£2 <'/•''' является обратимым в том и только том случае, если мо 7^ 0. С каждой последовательностью {ип} свяжем ряд

д(х) = щ + «1Ж + М2^2 + ...,который назовем производящей функцией для {ип}. Предположим, что по­следовательность {ип} является рекуррентной. Положим

1.

<р(х) = хг/(—) = 1 — о,\х — а<1Х — ■ ■ ■ — агх'

1 = 1 — (I | ■!' — (1->-1'~

'X

00

и рассмотрим произведение д(х) ■ (р(х) =      щх%) (1 — а\ж — ■ ■ ■ — агх

= щ + (щ — а\щ)х + («2 — сцщ — а2щ)х2 + • • • + (иг-\ — ауи,.--> — ■ ■ ■ —

■---аг-\щ)хг~1 + (иг — а\иг^1 — ■---аг- щ)хг + • • • + (ип+г — а1ип+/,—\ — ■ ■ ■ —

—аг • ип)хп+г + • • • = 6о + Ь\х + • • • + Ъг-\хг~1 = ф(х). Следовательно, у {ж) = |||| = (1_о,1а.)еУ.Ж(1_а<|а.)е,, • Правая часть этого равенства является пра­вильной дробью в Р(х) и, следовательно, разложима в сумму конечного числа простейших дробей, т.е. дробей вида        ^, где А £ ЁЛ < е^. Итак,

§11        _|__§12__[_____|__§1^1 |

дух

(1—»1ж)      (1^а1ж)2 (1^а1ж)е1

/?21 | /?22 | \ §2&2 \ | ^11

(1-«2а;)      (1^а2ж)2 (1^а2ж)е2

I /?81 I §82 I I /?«е8

(1—а8ж)      (1-а8х)2 (1-авх)ез

Так как

1      _ 1      и   т> (_/.)(_/._1)...(_/._(та_1)).аг»

- 1 - ий  ж + -     и (-1;   (.. ^ >

оо

то ^.дд,^ = /3 + XI (■'1'>~1— 1 • ^ -о" •Приравнивая коэффициенты при

п=1

в левой и правой части равенства (1), имеем, что

ип = ql{n)al + q2{n)a12l + ■■■+ &(п)а",

где дг(гг) - многочлен от п степени < — 1, коэффициенты которых опреде­ляются начальными значениями Щ), щ,..., иг^\ нашей последовательности. Таким образом, мы указали алгоритм вычисления членов рекуррентной по­следовательности с помощью производящих функций. Приведем примеры работы этого алгоритма.

Пример 1. Пусть щ = 1. и\ = 1, ип = ип^\ + ип^2, где п > 2 (последо­вательность Фибоначчи). Характеристический многочлен /(ж) = х2 — х — 1имеет корни а = -Цр^ и (3 = -Ц^. Следовательно,

00

/г(ж) = (1 — — (Зх) и д(ж) • /г(ж) =       ^тежте)(1 — ж — ж2) =

те=0

= «О + (^1 — щ)х + («2 — 1*1 — и)х2 + • • • = 1.

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

п(гЛ - 1 - ,  /?/(/?-<») _ А. Г_а___£_1 _

(1-ож)(1-/?ж)        (1-ах)        (1-/?ж)       у^^-ож (1-/?ж)]

= ^ [а(1 +     + а2ж2 + а3х3 Н----) - /3(1 + /Зж + (32х2 Н----)] =

= -^{(а — (3) + (а2 — (32)х + • • • + (ап+1 — (Зп+1)хп + •••}. Следовательно, = ±(ап+1 - /Зп+1) = ^{(^)п+1 - (^)п+1} (формула Вине). Замечание.  Укажем идею другого метода вычисления общего члена

рекуррентной последовательности порядка два на примере последователь­ности

щ = 1, Mi = 2, un+i = 8ип — 15«n_i, п > 1.

Найдем числа а, (3 такие, что 8 = а + (3, 15 = а/3 (ясно, что о = 3. :3 = о). Перепишем равенство ип+\ = 8ип — 15мте^1 в виде

un+i    5мте — 3(мте 5мте^1

un+i ~~ Змте = Ь(ип — Змте^1 Из последних равенств следует, что

un+i - Ъип = 3{3(мте^1 - 5мте^2)} = 32(мте^1 - 5мте^2

Un+i - Зип = Г>{Г>(</„_| - Змте^2)} = 52(мте^1 - Змте^2

3"+1^5"

= Зп^(и2 - 5mi) = Зп(м1 - 5м0) = -3n+1

= 5п(м1 - Зм0) = -5

п

Откуда следует, что ип = Пример 2. Рассмотрим рекуррентную последовательность порядка 3:

</о = +1, и 1 =5, «2 = Ю,

мте+3 = ип+2 + 5мте+1 + Змте, // > 0.

Найдем формулу //-ого члена этой последовательности. Заметим, что ха­рактеристический многочлен /(ж) = ж3 — х2 — Ъх — 3 имеет корни 3,-1,-1.

Поэтому (щ + щх + и2Х2 + ... )(1 — х — Ъх2 — Зж3) = щ + (щ — щ)х+ + («2 — Щ — 5щ)х2 + 0 • х'л + 0 • 1 + • • • = 1 + 4х. Следовательно, произ­водящая функция д(х) равна дроби (хгщ^^р- Разложим эту правильную дробь в сумму простейших

1 + 4;/;        _      А В С

(1 -Зх)(1 + х)2 ~ (1 - Зж) + (1 + ж) + (1 + ж)2'

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

А+В+С=1 А - ЗВ = О 2А - 2В - ЗС = 4,

из которой следует, что А = 21/16, Б = 7/16, С = —3/4. Следовательно, д(х) = 1 + Ъх + ••• + (§• Зп + ^(-1)п + |(п + 1)(-1)п+1)хп + .... Поэтому ип = I • Зп + ^(-1)п + |(п + 1)(-1)п+1, где п > 0.

ЗАДАЧИ

1) . Найти общий член следующих рекуррентных последовательностей

а) </о = —2, «1 = 3, мте+1 = 10ип — (.Уи„-\. п > 1;

б) «о =1.^/1= 2, «2 = 0, из = —1,

ип+4 = Змте+3 + Змте+2 - 7ип+г - 6ип, п > 0.

2) . Сколькими способами можно расставить скобки в (неассоциативном) слове 0,10,2 ... ап?

УКАЗАНИЕ. Обозначим через ип число таких способов. Положим </о = 0, щ = 1. Тогда «2 = 1, *</.->, = 2, </1 = 5, так как имеем следующие расстановки скобок

(0,10,2)0,3,0,1(0,20,3), ((0102)03)04, (0102)^304), 01(02(0304)), (а1(а2аз))а4, а1((а2аз)а4).

Заметим, что ип = и\ип^\ + и->и,,^-> + • • • + у/„_г</|. п > 2. Из этого равен­ства следует следующее соотношение для производящей функции /(ж) =

00 _ -

= ]Г щхг : /(ж)2 = /(х) — х. Откуда следует, что /(х) = 1   ^^4ж (ряд /(х)

удовлетворяет условию /(0) = 0). Следовательно, ип = ^™п-\)\> " — -• 3). (Задача о встречах). Некто написал гг писем и запечатал их в конверты, не надписав предварительно адресов. После этого он уже не знал, в каком конверте лежит какое письмо, и поэтому п адресов на конвертах написал наугад. Какова вероятность того, что хотя бы один из адресатов получит предназначенное для него письмо?

УКАЗАНИЕ. Обозначим через Ап число исходов, при которых ни один конверт не будет подписан правильно. Тогда искомая вероятность равна (1 — ^т). Вычислим число Ап. Для этого заметим, что

Ап = (п- 1)(Ап_і + Ап_2).

При неблагоприятном исходе на 1-м конверте (т.е. в нем находится пись­мо, отправлемое по первому адресу) может быть написан 2-й, 3-й, ..., п-й адрес. Пусть, например, написан 2-й адрес. Если на 2-м конверте написан 1-й адрес, то для остальных (п — 2) конвертов мы имеем Ап^2 неблагопри­ятных возможностей. Если же на 2-м конверте разрешается писать только 3-й, 4-й, п-й адреса, то таких возможностей у нас Ап^\. Итак, общее чи­сло неблагоприятных возможностей, при которых на первом конверте под­писывается второй адрес, равно (Ап-\ +Ап-ъ). Такие же числа мы получим, подписывая первый конверт 3-м, 4-м,..., /7-м адресами. Следовательно,

Ап = (п- 1)(Ап_і + Ап_2).

Откуда следует, что Ап - пАп^ = -(Ап^ - (п - 1)Ап^2) = = К-2 - {п- 2) А»-з = • • • = Ы)^'2(Л, - 2-'Ь) = (-1)п, т.к. А\ = 0. Л, = 1. Рассмотрим равенства:

Ап = пАп^ + {-1)п 16

Ап_1 = (п-1)Ап_2 + (-1)

А, = ЗАо + (-1

Умножим второе равенство на п, третье - на п(п — 1),... и сложим. Полу­чим следующее равенство:

г1     1     1 (-^1 ,

Искомая вероятность равна

1 -     = 1 - - + ------К-^- -+ 1 - е^1 « 0,6.

п! 2!    3! п!

4). Найти производящие функции следующих последовательностей:

а)

/ 1, п = 0,1,...,ЛГ,

[О, п > N. ОТВЕТ: #(ж) = 1 + х + • • • + хм.

б)

{О, п — четное ,

п ///!. п — нечетное . УКАЗАНИЕ. д(х) = % ■ х + ^ж3 + • • • = «аа-«"аа. в) ите = тг-мте, если #(ж) - известная производящая функция последователь­ности {мте}.

оо

УКАЗАНИЕ. Н(х) = £ г,,/;" = 0+ </,;»; + 2м2ж2 + • • • =

те=0

= Ж • («1 + 2щХ + Змзж2 + ...)= Ж • (д(ж)'

г) уп = мте+1 — ип: если д(ж) - известная производящая функция последова­тельности {ип}. УКАЗАНИЕ.

Н(х) = (щ - щ) + (щ - щ)х + (щ - щ)х2 Н----= ... 9^~9^ - #(ж).

5). Пусть {ип} такая последовательность элементов поля .Р, что произво­дящая функция д(х) является правильной дробью вида

1 + а,\х + • • • + агхг

Доказать, что {ип} - рекуррентная последовательность порядка г. УКАЗАНИЕ. Из равенства

д(х)(1 + а\х + • • • + агхг) = (6о + Ъ\ + • • • + ЬГ^1ХГ^1) следует, что

= 0,тг > 0.

6) . Найти общие решения рекуррентных соотношений:

а) ап+2 - 4ап+г + Зап = 0;

б) ате+з + Зате+2 + Зате+1 + ап = 0;

в) оте+з — Зате+2 + ап+\ — Зап = 0, а\ =3, а-) = 7, аз = 27;

г) ате+2 — 2сова ■ ап+\ + ате = 0, а1 = сова, аг = сов2а.

7) . Решить рекуррентные соотношения:

а) ап+г - ап = п} аг = 7;

б) ап+2 + 2ате+1 - 8ате = 27 • Г>". а\ = -9, а2 = 45.

8) . Найти последовательность {ап}, члены которой удовлетворяют соот­ношениям:

а) аоате + а\ап^1 + • • • + атеао = 2теате, ао = а\ = 1;

б) ап+2 • (га + 2)2 + ап = 0, а0 = 1, а! = 0.

УКАЗАНИЕ для а). Рассмотрим ряд /(;/;) = ^ а/./;'. Тогда /(ж)2 = /(2;/;

Из соотношений а) следует, что если решение существует, то оно единствен­ное. Положим /(х) = еХх. Тогда (еЛж)2 = ех^2х\ Так как

00

п=0

^   Аж А 1 1

с   = Ъ   ы-' то положим    = <ц = 1, «„ = ^.

ОТВЕТ для б): а->\,-\ = 0, а2,

(-1)".4~п

', —        („1)2 •

9). Пусть ап - число решений в целых неотрицательных числах уравнения

2;/; + Ъу + 7,: = п. Доказать, что

00

^2 апхп = (1 - х2У\\ - хьУ\\ - х

п=0