302
правки
Изменения
Новая страница: «==Определения== {{Определение |definition= '''Рекуррентная формула''' — формула вида <math>a_n=f(n, a_{n-1}…»
==Определения==
{{Определение
|definition=
'''Рекуррентная формула''' — формула вида <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 > 0 \end{cases}</math>
может быть переведена в замкнутую форму: <math>f = \frac{n(n+1)}{2}</math>. Для этого можно использовать метод производящих функций.
==Метод производящих функций==
..алгоритм
==Доказательство==
по построению
==Примеры==
{{Определение
|definition=
'''Рекуррентная формула''' — формула вида <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 > 0 \end{cases}</math>
может быть переведена в замкнутую форму: <math>f = \frac{n(n+1)}{2}</math>. Для этого можно использовать метод производящих функций.
==Метод производящих функций==
..алгоритм
==Доказательство==
по построению
==Примеры==
