Рассмотрим обобщение последовательностей Фибоначчи. Формула
un + r = c1 un + r – 1 + c2 un + r – 2 + …+ cr un
называется однородным линейным рекуррентным уравнением порядка r. Ее решением является последовательность {un}, однозначно определенная начальными значениями u0, u1, u2, …∙, ur –1. Решение такого уравнения называется возвратной, или рекуррентной последовательностью порядка r.
Пример 1
Геометрическая прогрессия является решением уравнения un+1 = qun. Ее члены описываются формулой un = u0qn. Отсюда геометрическая прогрессия является возвратной последовательностью порядка 1.
Пример 2
Арифметическая прогрессия un = u0 + nd удовлетворяет соотношению:
un+1 - un = un+2 - un+1.
Получаем однородное рекуррентное уравнение:
un+2 = 2un+1 - un.
Начальные данные задаются значениями u0 и u1 = u0 + d. Отсюда, арифметическая прогрессия является возвратной последовательностью порядка 2.
Пример 3
Произвольная периодическая последовательность является возвратной последовательностью порядка p, удовлетворяющей рекуррентному соотношению:
un + p=un.
Здесь p – период последовательности.
Для заданного рекуррентного уравнения
un + r = c1 un + r – 1 + c2 un + r – 2 + …+ cr un
найдем производящую функцию 
возвратной последовательности {un}.
Обозначим:
K(x) = 1- c1x - c2x2 -… - crxr.
Теорема 1
Произведение u(x)K(x) = D(x) является многочленом степени, меньшей r.
Доказательство
Вычислим коэффициент ряда D(x) при xn+ r. Он при n ≥ 0 будет равен:
un + r - (c1 un + r – 1 + c2 un + r – 2 + …+ cr un) = 0.
Отсюда D(x) – многочлен степени, меньшей чем n.
Замечание
Частное от деления любых двух многочленов является производящей функцией некоторой возвратной последовательности, порядок которой равен степени знаменателя.
Пример 4
Применим доказанную теорему к решению рекуррентного уравнения
un+2 = 5 un+1 - 6 un
при начальных условиях u0 = u1 = 1.
Здесь K(x) = 1 - 5x + 6x2.
Вычислим:
D(x) = K(x)u(x) = (1 - 5x+6x2)(u0 + u1x + … ) = (u0 - 5u0 x + u1x +…).
По теореме 1 коэффициенты при x2, x3… равны нулю, а u0 = u1 = 1. Следова
тельно,
D(x) = (1 -5 x + x) = 1 - 4x.
Получаем:
.
Следующий шаг – разложение знаменателя K(x) в произведение
(1 - a1x) (1- a2x).
В данном случае это можно сделать с помощью формулы Виеты. Поскольку имеют место равенства:
a1 + a2 = 5; a1 a2 = 6,
то числа a1 и a2 будут корнями квадратного уравнения a2 - 5a +6 = 0. Решая это квадратное уравнение, получаем:
.
Приходим к формуле
.
Теперь найдем разложение в сумму простых дробей методом неопределенных коэффициентов:
.
Получим систему линейных уравнений:
имеющую решение A = 2, B = -1. Отсюда
.
Это приводит к ответу
un = 2n+1-3n.
В общем случае числа aI в разложении
K(x) = (1 - a1x) (1- a2x) … (1 - arx)
являются корнями уравнения:
F(a)=a r- c1a r -1 - … - cr-1a - cr = 0,
ибо K(x) = 
. Это уравнение F(a) = 0 называется характеристическим.
Если все корни уравнения F(a)=0 действительны и различны, то получаем:
,
откуда
.
Это позволяет составить систему линейных уравнений для нахождения Ai с помощью известных значений u0, u1, …∙, ur-1.
Пример 5
Рассмотрим рекуррентное уравнение:
при заданных u0 = 2, u1=1.
Составим характеристическое уравнение:
F(a) = a2 + a - 2 = 0.
Его корни a 1 = 2, a 2 = -1 не равны между собой и являются вещественными числами. Поэтому решение рекуррентного уравнения можно искать в виде:
.
Значения un известны при n = 0, 1, откуда получаем систему линейных уравнений для нахождения коэффициентов A1, A2:
Решаем эту систему уравнений:
получаем A1 = A2 = 1. Приходим к следующему ответу:
.
Если существуют кратные корни, то, пользуясь формулами для производных от геометрической прогрессии, можно доказать, что решение будет дополняться слагаемыми:
,
где k – кратность корня 
.
Пример 6
Решим рекуррентное уравнение:
, u0 = 1, u1 = 6.
С этой целью составим характеристическое уравнение:
a2- 6a +9=0.
Оно имеет кратные корни a 1 = a 2 =3. Поэтому решение рекуррентного уравнения нужно искать в виде
un = A13n + A2 n 3n
Подставляя известные значения u0 = 1 и u1 = 6, приходим к системе уравнений
Она имеет решение A1 = A2 = 1. Получаем ответ:
un = 3n(1 + n).
Упражнения
Свойства производящих функций
1. Сколько делителей, включая само число и 1, имеет число 720?
2. Доказать, что при n > 0 имеют место соотношения:
1) 
;
2) 
.
3. Найти производящую функцию последовательности an = 10ncos(2n).
4. Найти производящую функцию последовательности an = 10nsin(2n).
5. Найти производящую функцию последовательности an = 10nn.
6. Найти производящую функцию последовательности an = 10nn.
7. Найти производящую функцию последовательности an = 10nn(n+1).
8. Найти производящую функцию последовательности an = 10nn2.
9. Найти производящую функцию последовательности an = 10n/(n+1).
10. Найти производящую функцию последовательности an = 10n/(n+1)(n+2).
11. Доказать рекуррентное соотношение для производящих функций последовательностей nk:
.
12. Найти производящие функции последовательностей an = nk, при k = 1, 2, 3, 4.
Решение рекуррентных уравнений
13. un+2 = un+1 + 2un, u0 = 1, u1 = 1.
14. un+2 = -un+1 + 2un, u0 = 0, u1 = 1.
15. un+2 = -3un+1 – 2un, u0 = 1, u1 = 1.
16. un+2 = un+1 + 6un, u0 = a, u1 = b.
17. un+2 – 4un+1 – 5un = 0, u0 = 8, u1 = 10.
Ответ: un = 7+3n
18. un+3 – 3un+2 +un+1– 3un = 0, u0 = 1, u1 = 3, u2 = 8.
Ответ: u2n= (9×32n+(-1)n)/10, u2n+1= (9×32n+1+3×(-1)n)/10, n≥0.
19. un+3 + un+2 – un+1– un = 0, u0 = 1, u1 = 2, u2 = 3.
Ответ: un=(-1)n(n-1)+2
20. un+2 – 4un+1 + 4un = 0, u0 = a, u1 = b.
21. un+2 = 2un+1 – 2un, u0 = 1, u1 = 2.
Указание: Производящая функция последовательности un:
u(x)= 
.
Ответ: 
22. un+3 = 3un+2 – 3un+1+ un, u0 = 1, u1 = 3, u2 = 3;
Указание: Искать решение в виде: un=A+ Bn + Cn2.
23. un+3 = – 3un+2 – 3un+1– un, u0 = 0, u1 = 1, u2 = –2.
24. un+2 = un+1 – un, u0 = 1, u1 = 9. Ответ: 
25. un+2 = 2un+1 – 4un, u0 = 1, u1 = 2. Ответ: 