В чем заключается метод рекуррентных соотношений для решения задач по математике?

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

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

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

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

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