- •4. Рекуррентные последовательности и производящие функции §4.1. Линейные рекуррентные соотношения
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§4.2. Производящие функции
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§4.3. Числа Фибоначчи
- •Свойства чисел Фибоначчи
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •1. Множества и математическая логика
- •2. Метод математической индукции
- •3. Элементы комбинаторики
- •4. Рекуррентные последовательности и производящие функции
- •Литература
Вопросы и упражнения для самостоятельной работы
Найти общий вид членов последовательности (un), удовлетворяющей соотношению
un+2 = 5un+1 – 6un,
если u0 = 2, u1 = 5.
Найти общий вид членов последовательности (un), удовлетворяющей соотношению
un+2 = un+1 + 3un,
если u0 = 2, u1 = 2.
Найти общий вид членов последовательности (un), удовлетворяющей соотношению
un+2 = 6un+1 – 9un,
если u0 = 2, u1 = 9.
Найти общий вид членов последовательности (un), удовлетворяющей соотношению
un+2 = –2un+1 – un,
если u0 = 5, u1 = –7.
Найти общий вид членов последовательности (un), удовлетворяющей соотношению
un+2 = 4un+1 – 5un,
если u0 = 4, u1 = 8.
Найти общий вид членов последовательности (un), удовлетворяющей соотношению
un+2 = 4un+1 – 5un,
если u0 = 2, u1 = 2 + 2.
Найти рекуррентное соотношение и общий вид членов последовательности сумм
sn = u0 + u1 + …+ un,
где (un) – рекуррентная последовательность такая, что
u0= 3;u1= 5;un+2 = 3un+1 – 2un.
Найти рекуррентное соотношение и общий вид членов последовательности сумм
sn = u0 + u1 + …+ un,
где (un) – рекуррентная последовательность такая, что
u0= –1;u1= 1;un+2 = –5un+1 – 3un.
Найти формулу для вычисления суммы кубов натуральных чисел 13+ 23+ …n3.
Найти рекуррентное соотношение для членов последовательностиun = n(n + 1).
§4.2. Производящие функции
Производящей функциейчисловой последовательностиa0, a1, …, ak, … называется ряд
.
Если последовательность конечна или, начиная с некоторого места, все ее члены равны нулю, то пишут также
f(z) = ,
предполагая, что члены последовательности с номерами больше чем nотсутствуют или равны нулю. Говорят, что производящая функция представленав замкнутом виде, если дляf(z) указано конечное аналитическое выражение.
В таблице 1 приведены производящие функции некоторых последовательностей.
Если f(z) – производящая функция последовательностиa0, a1, …, ak, … , то функцияf(z) – производящая функция последовательностиa0, a1, …, ak, … , а производная (z) – производящая функция последовательностиa1, 2a2, …, kak, … .
Если f(z) иg(z) – производящие функции соответственно последовательностейa0, a1, …, ak, … иb0, b1, …, bk, … , тоf(z) + g(z) – производящая функция последовательностиa0 + b0, a1 + b1, …, ak + bk, … .
Таблица 1
Последовательность |
Производящая функция |
Замкнутый вид |
1,2,1,0,0,… |
1 + z +z2 |
1 + z +z2 |
1,1,1,1,… | ||
1,–1,1,–1,… | ||
1,0,1,0,… | ||
1,2,4,8,16,… | ||
1,2,3,4,… | ||
1,1,,,… |
ez | |
0,1,,,… |
Сверткойпоследовательностейa0, a1, …, ak, … иb0, b1, …, bk, … называется последовательностьc0, c1, …, ck, … такая, что
c0 = a0b0, c1 = a0b1 + a1b0 ,
и, вообще,
ck = .
Если f(z) иg(z) – производящие функции последовательностей (ak) и (bk), то производящей функцией их свертки является произведениеf(z)g(z).
Производящая функция f(z) рекуррентной последовательности, удовлетворяющей соотношению
un+r = a1un+r–1 + a2un+r–2 +…+ arun ,
имеет следующий вид, где
h(z) = 1 – a1z – a2z2 –…– arzr ,
а g(z) – многочлен степени не выше, чемr – 1.
Примеры
1.Найти производящую функцию следующей последовательности
ak =
Решение. Имеем:
f(z) = 1 + z + z2 + … + zn.
В правой части равенства, определяющего производящую функцию, – сумма членов геометрической прогрессии со знаменателем z. Суммируя, получаем
f(z) = .
2.Найти производящую функцию следующей последовательности
ak =
Решение. В соответствии с определением
f(z) = 1 + 2z + 3z2 + … + (n + 1)zn.
Правая часть этого равенства является производной суммы
1 + z + z2 + … + zn + zn+1 ,
которую вычисляем как сумму геометрической прогрессии:
1 + z + z2 + … + zn + zn+1 = .
Следовательно,
f(z) = = .
3.Найти производящую функцию последовательности
ak = k2.
Решение. В соответствии с определением
f(z) =z + 4z2 + … + n2zn + … .
Рассмотрим следующую сумму:
g(z) = 21 + 32z + … + n(n – 1)zn–2 + …
Ряд в правой части получается в результате двукратного дифференцирования ряда
p(z) = 1 + z + z2 + … + zn + … .
Сумма последнего ряда вычисляется как сумма геометрической прогрессии:
p(z) = .
Следовательно,
g(z) = p(z) = = .
Умножим g(z) наz2:
z2g(z) = 10z + 21z2 + 32z3 + … + n(n – 1)zn + … .
Рассмотрим ряд
h(z) = z + 2z2 + 3z3 + … + nzn + … .
Очевидно,
f(z) = z2g(z) + h(z).
Чтобы вычислить сумму ряда h(z) заметим, что
p(z) = 1 + 2z + 3z2 + … + nzn–1 + … ,
так что h(z) получается умножениемp(z) наz. Значит,
h(z) = zp(z) = = .
Окончательно получаем:
f(z) = + = .
4.Найти производящую функцию следующей рекуррентной последовательности
u0 = 1,u1 = 2,uk+2 = uk+1 + 2uk .
Решение. Найдем выражение для производящей функции непосредственно (без обращения к формуле из теоретического введения). По определению
f(z) = u0 + u1z + u2z2 + … .
Имеем:
zf(z) = u0z + u1z2 + u2z3 + … ;
2z2f(z) = 2u0z2 + 2u1z3 + 2u2z4 + … .
Отсюда
f(z) – zf(z) – 2z2f(z) = u0 + (u1 – u0)z + (u2 – u1 – 2u0)z2 + … .
В силу рекуррентного соотношения коэффициенты при всех степенях zk, начиная сk = 2, равны нулю. Таким образом,
f(z) – zf(z) – 2z2f(z) = u0 + (u1 – u0)z .
Значит,
f(z) = .
5.Для заданной рекуррентной последовательности
u0 = 1,uk+1 = 2uk+1 + 3k
найти производящую функцию и получить формулу общего члена последовательности.
Решение. По определению
f(z) = u0 + u1z + u2z2 + … .
Тогда
2zf(z) = 2u0z + 2u1z2 + 2u2z3 + …
и
f(z) – 2zf(z) = u0 + (u1 – 2u0)z + (u2 – 2u1)z2 + … =
= 1 + 3z + 32z2 + … .
Таким образом, f(z) – 2zf(z) является суммой членов геометрической прогрессии со знаменателем 3z, так что
f(z) – 2zf(z) = .
Отсюда
f(z) = .
Теперь разложим дробь в правой части на простейшие дроби:
= – .
Полученные дроби раскладываем в ряд, используя формулу для суммы геометрической прогрессии:
= 3(1 + 3z + 32z2 + … ) = 3 + 32z + 33z2 + … ;
= 2(1 + 2z + 22z2 + … ) = 2 + 22z + 23z2 + … .
С учетом этого
f(z) = .
Следовательно,
uk = 3k+1 – 2k+1.
6.Найти сумму
.
Решение. Воспользуемся производящими функциями. Рассмотрим бином
(1 + z)n = .
Коэффициент при znв произведении
(1 + z)n(1 + z)n =
= ()()
равен сумме
.
Заметим, что = , = , и, вообще, = . Значит,
= .
С другой стороны,
(1 + z)n(1 + z)n = (1 + z)2n,
и коэффициент при znможно найти, применив формулу Ньютона к биному (1 +z)2n: коэффициент равен . С учетом этого получаем
= .
7.Найти число целых решений уравнения
x1 + x2 + x3 + x4 = 20
при условии, что 0 xi 10,i = 1, 2, 3, 4.
Решение. Для решения задачи воспользуемся производящими функциями. Обозначим черезakчисло целых решений уравнения
x1 + x2 + x3 + x4 = k,
для которых 0 xi 10,i = 1, 2, 3, 4. С учетом этих обозначений,a20– искомое число. Рассмотрим произведение
(1 + z + z2 + … + z10)4.
Слагаемые, которые получаются после непосредственного раскрытия скобок (до упрощений) имеют вид , где 0xi 10. Коэффициент приzkравен числу слагаемых вида, для которыхx1 + x2 + x3 + x4 = k. Следовательно, этот коэффициент равенak. Таким образом,
(1 + z + z2 + … + z10)4 = a0+a1z+ a2z2+ … + a40z40.
Преобразуем левую часть полученного равенства:
(1 + z + z2 + … + z10)4 = = (1 – z11)4(1 – z)–4 =
= (1 – 4z11 + 6z22 – 4z33 + z44)(1 + 4z + 10z2 + 20z3 + … ).
Заметим, что вторая сумма получена как разложение в ряд бинома (1 – z)–4 , и слагаемые имеют вид (–1)j. Найдем коэффициент приz20:
a20=+ 4.
Учитывая, что =, получаем:
a20=– 4= 1771 – 4220 = 891.
8.Сколькими способамиnразличных предметов можно разложить по трем ящикам так, чтобы в первом находился хотя бы один предмет, во втором – нечетное число предметов, в третьем – четное число предметов.
Решение. Обозначим искомое число черезpn. Сначала определим, сколькими способами можно разложить предметы по ящикам так, чтобы в первом былоn1предметов, во втором –n2предметов, в третьем –n3предметов (при условии, что разложены все предметы, то естьn1+n2+n3=). Искомое число можно рассматривать как число перестановок с повторениями из трех ящиков поn, в которые первый ящик входитn1раз, второй –n2раз, третий –n3раз. Это число есть
P(n1, n2, n3) = .
Рассмотрим следующую функцию, представляющую собой произведение трех рядов:
f(z) =
=.
Если раскрыть скобки (не приводя подобные), число слагаемых вида (обозначим его черезan) равно числу способов представитьnв виде суммыn1+n2+n3=nтак, чтобыn1было положительным,n2– нечетным,n3– четным. Тогдаn!an– это искомое числоpn. Значит, если разложить функциюn!f(z) в степенной ряд, то коэффициент приznравенpn, то естьn!f(z) является производящей функцией последовательностиp0,p1,p2, … :
n!f(z) = p0 + p1z + p2z2+… .
Воспользуемся степенным рядом для ez:
ez=.
Замена zна –zдает следующее равенство:
e–z=.
С учетом этого получаем:
= ez– 1;
= ;
= .
Таким образом,
f(z) = (ez– 1)= (e3z–e2z–e–z+e–2z).
Так как ekz– производящая функция последовательности, тоf(z) – производящая функция последовательности
.
Но тогда n!f(z) – производящая функция последовательности
(3n – 2n – (–1)n + (–1)n2n),
так что
pn = (3n – 2n – (–1)n + (–1)n2n).
Если nчетно, то
pn = (3n –1),
если nнечетно, то
pn = (3n – 2n+1 +1).