Рекуррентные соотношения. Возвратные последовательности

Рекуррентной формулой называется соотношение вида a_n+k =F (n, a_n,a_n+1,...,a_n+k-1), которое позволяет вычислять все члены последовательности а₀,а₁,а₂, …, если заданы её первые k членов.

В случае, когда рекуррентное соотношение линейно и однородно, т.е. выполняется соотношение вида а_n+k+p₁a_n+k-1+...+p_ka_n=0 (p = const), последовательность a₀,a₁,a₂,... называется возвратно й. Многочлен

называется характеристическим для возвратной последовательности { а_n }. Корни многочлена Р_а(х) называются характеристическими.

Множество всех последовательностей, удовлетворяющих данному рекуррентному соотношению, называется общим решением.

Описание общего решения зависит от корней характеристического многочлена.