Решение рекуррентных соотношений — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определения== {{Определение |definition= '''Рекуррентная формула''' — формула вида <math>a_n=f(n, a_{n-1}…»)
(нет различий)

Версия 16:48, 12 марта 2018

Определения

Определение:
Рекуррентная формула — формула вида [math]a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) [/math], выражающая каждый член последовательности [math]a_n[/math] через [math]p[/math] предыдущих членов и возможно номер члена последовательности [math]n[/math].


Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма, т.е. получение [math]f(n)[/math] в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

[math] f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n \gt 0 \end{cases}[/math]

может быть переведена в замкнутую форму: [math]f = \frac{n(n+1)}{2}[/math]. Для этого можно использовать метод производящих функций.

Метод производящих функций

..алгоритм

Доказательство

по построению

Примеры