9. Понятие рекуррентного соотношения. Рекуррентное соотношение k-го порядка для функции одной переменной, его общее решение.

Рекуррентноe соотношениe- соотношение между элементами последовательности, в которой следующий элемент выражается через несколько предыдущий. 

Рекурентная формула — формула вида  , выражающая каждый член последовательности   через p предыдущих членов. Например - числа Фибоначчи 

Линейным рекуррентным соотношением k - го порядка(k - фиксировано) с постоянными коэффициентами называется рекуррентное соотношение следующего вида:

            (3)

 - постоянные  .

Характеристическим уравнением рекуррентного соотношения (3) является уравнение вида

     Теорема 2: Пусть   - все попарно различные корни характеристического уравнения рекурретного соотношения (3)   - кратность корня  . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

  .

В частности, если  , то

---------------------------------------------------------------------------------------------------------------------------------------