Рекуррентное отношение
В математике рекуррентное отношение — это уравнение , выражающее n -й член последовательности как функцию k предшествующих членов для некоторого фиксированного k (независимого от n ), которое называется порядком отношения. Когда задано k начальных членов последовательности, рекуррентное соотношение позволяет рекурсивно вычислить все члены последовательности.
Наиболее общие результаты о рекуррентных соотношениях относятся к линейным рекуррентным отношениям, которые представляют собой рекуррентные отношения, в которых n -й член является линейным по отношению к его предыдущим терминам. Среди них особенно важны линейные рекурренты с постоянными коэффициентами и линейные рекурренты с полиномиальными коэффициентами . В первом случае это связано с тем, что можно выразить общий член последовательности как выражение в замкнутой форме индекса члена. Во втором случае это связано с тем, что многие обычные элементарные и специальные функции имеют ряды Тейлора , коэффициенты которых удовлетворяют такому рекуррентному соотношению (см.голономная функция ).
Концепцию можно распространить на многомерные массивы , то есть индексированные семейства , которые индексируются кортежами натуральных чисел .
Рекуррентное соотношение — это уравнение, выражающее каждый элемент последовательности как функцию предыдущих. Точнее, в случае, когда задействован только непосредственно предшествующий элемент, рекуррентное соотношение имеет вид
— функция, где X — множество, которому должны принадлежать элементы последовательности. Для любого это определяет уникальную последовательность с первым элементом, называемым начальным значением . [1]
Легко изменить определение для получения последовательностей, начинающихся с термина индекса 1 или выше.