Решение рекуррентных соотношений

Будем говорить, что рекуррентное соотношение имеет порядок

$Решение рекуррентных соотношений$

, если оно позволяет выразить

$Решение рекуррентных соотношений$

через

$Решение рекуррентных соотношений$

. Например,

$Решение рекуррентных соотношений$

рекуррентное соотношение второго порядка, а

$Решение рекуррентных соотношений$

- рекуррентное соотношение третьего порядка. Если задано рекуррентное соотношение

$Решение рекуррентных соотношений$

-го порядка, то ему удовлетворяет бесконечно много последовательностей. Дело в том, что первые

$Решение рекуррентных соотношений$

элементов последовательности можно задать совершенно произвольно - между ними нет никаких соотношений. Но если первые

$Решение рекуррентных соотношений$

элементов заданы, то все остальные элементы определяются совершенно однозначно - элемент

$Решение рекуррентных соотношений$

выражается в силу рекуррентного соотношения через

$Решение рекуррентных соотношений$

элемент

$Решение рекуррентных соотношений$

- через

$Решение рекуррентных соотношений$

и т.д.

Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, причем рано или поздно получим любой ее член. Однако при этом придется выписать и все предыдущие члены - ведь не узнав их, мы не узнаем и последующих членов. Но во многих случаях нужно узнать только один определенный член последовательности, а остальные не нужны. В этих случаях удобнее иметь явную формулу для

$Решение рекуррентных соотношений$

-го члена последовательности. Некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется. Например, последовательность

$Решение рекуррентных соотношений$

является одним из решений рекуррентного соотношения

$Решение рекуррентных соотношений$

В самом деле, общий член этой последовательности имеет вид

$Решение рекуррентных соотношений$

. Значит,

$Решение рекуррентных соотношений$

. Но при любом

$Решение рекуррентных соотношений$

имеет место тождество

$Решение рекуррентных соотношений$

. Поэтому

$Решение рекуррентных соотношений$

является решением указанного соотношения.

Решение рекуррентного соотношения

$Решение рекуррентных соотношений$

-го порядка называется общим, если оно зависит от

$Решение рекуррентных соотношений$

произвольных постоянных

$Решение рекуррентных соотношений$

и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения

$Решение рекуррентных соотношений$

(8.1)

общим решением будет

$Решение рекуррентных соотношений$

(8.2)

В самом деле, легко проверить, что последовательность (8.2) обращает (8.1) в тождество. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде (8.2). Но любое решение соотношения (8.1) однозначно определяется значениями

$Решение рекуррентных соотношений$