Метод рекуррентных соотношений для решения задач по математике заключается в том, что он позволяет свести решение задачи к аналогичной задаче для меньшего числа предметов. 45 Например, задачу об n-предметах сводят к задаче о n-1 предметах, потом к задаче о n-2 и так далее, последовательно уменьшая число предметов, пока не дойдут до задачи, которую уже легко решить. 4

Для решения рекуррентных соотношений применяют один из двух основных способов: 2

1. Метод производящих функций. 12 Алгоритм получения выражения для чисел, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из четырёх шагов: 1

• Записать рекуррентное соотношение и начальные данные для него. 1
• Домножить каждую строчку на z в соответствующей степени и сложить все выражения. 1 В левой части получится сумма — это производящая функция, назовём её G(z). 1
• Преобразовать правую часть так, чтобы она превратилась в выражение, включающее G(z). 1
• Решить полученное уравнение, получив для G(z) выражение в замкнутом виде. 1
• Разложить G(z) в степенной ряд, коэффициент при zn будет искомым выражением для an. 1

1. Метод характеристических функций. 2 Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами. 2