На этом шаге мы дадим краткую формулировку этого метода.

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

    T(n) = - a₁T(n - 1) - ... - a_kT(n - k)	{"T-разности"}
           + P₁^d₁(n)b₁ⁿ + ... + P_s^d_s(n)b_sⁿ {полином * экспонента}, (3.33)

где a_i и b_i - константы, а P_i^d_i(n) - полиномы от n степени d_i. Слагаемые правой части определения (уравнения), содержащие функцию T(), могут встречаться несколько раз. Кроме того, их параметром обязательно должна быть разность n и некоторой целочисленной константы. Поэтому такие рекуррентные соотношения обычно называют "разностными уравнениями", а их T-члены - "T-разностями", чтобы подчеркнуть, что аргументы функции T() не могут быть дробями вида n/b, где b - константа (в противном случае их следует привести к виду (3.33)). Кроме того, в правой части определения может быть несколько слагаемых, представляющих собой произведения полинома на экспоненту степени n.

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

На следующем шаге мы рассмотрим однородные рекуррентные соотношения.

Предыдущий шаг Содержание Следующий шаг