Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 244 стр.

244                   Теория определителей                      Гл. 4

  Определение 30a.1. Под рекуррентностью порядка d мы бу-
дем понимать числовую последовательность {uk }∞k=1 , каждый член
которой, начиная с ud+1 , определяется d предыдущими членами с
помощью рекуррентной формулы
               uk = F (uk−1 , uk−2 , ..., uk−d ); k > d + 1,   (30a.1)
где F — заданная функция от d переменных.
   Любая последовательность, удовлетворяющая всем соотношени-
ям (30а.1), называется решением рекуррентности.
  Замечание 30а.1. Ясно, что все члены последовательности {uk }
будут однозначно определены, если произвольным образом задать
первые d ее членов. Обычно это делается в форме так называемых
начальных условий:
                    u1 = u01 ; u2 = u02 ; ...; ud = u0d .      (30a.2)
   Решить рекуррентность (30а.1) — это значить найти все ее ре-
шения. Формула, содержащая все частные решения рекуррентно-
сти [т. е. решения всевозможных начальных задач (30а.1)—(30a.2)]
называется ее общим решением. Такая формула, как правило, со-
держит d произвольных констант C1 , C2 , ..., Cd , которые могут быть
определены, если заданы конкретные начальные значения u0i , ..., u0d .
   Рекуррентности очень часто встречаются как в математике, так
и в компьютерных науках. Далеко не всегда удается решить их
явно, т. е. получить ответ в виде формулы, определяющей uk как
функцию от номера k. Чаще всего приходится удовлетвориться про-
цедурой (программой), позволяющей, в принципе, вычислить любой
член последовательности с наперед заданным номером. (Разумеется,
все такие "принципиальные возможности" на практике ограничены
быстродействием и объемом памяти компьютера.)
   Еще одна необходимая оговорка: нумерация членов последова-
тельности совсем не обязательно начинается с единицы; часто на-
чальным номером служит 0, но допустимо и любое другое целое
число.
  Пример 30а.1. Рекуррентная формула (порядка d = 1)
                      uk = kuk−1 ; k > 1; u0 = 1               (30a.3)
задает не что иное, как факториал: uk = k!
  [Не подумайте только, что рекуррентность (30а.3) здесь "решена"!
Мы лишь пересказали определение факториала. А рекуррентность
задает процедуру для его вычисления.]