Доказательство

Пусть

то есть получили аналог

Правила решений рекурсивных соотношений вида (2)

Для соотношения (2) составленное квадратное уравнение вида (3) называется характеристическим, если это уравнение будет иметь 2 различных корня и то общее решение (2) будет иметь вид

(4)

Любое решение рекурсивного соотношения однозначно определено двумя значениями , подставим их в уравнение (4) получим:

(5)

Получили линейное уравнение

Общее решение этой системы будет:

Решение имеет место для любых a и b и можно всегда найти значение и то есть решение всегда есть и имеет единственное значение в результате его можно представить в виде уравнения (4)

Пример: Пусть дано уравнение – Рекурсивное соотношение 2-го порядка. Если положив в это уравнение и , то в результате получим рекурсивное соотношение которое определяет последовательность чисел полученных Фибоначчи.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 59, 144, 233.

Эта последовательность используется при кодировании информации.

Характеристическое уравнение для этой последовательности чисел будет:

, где , а

Общее решение:

Требуется найти значения и соответственно заданным начальным требованиям:

Берем n = 1

Итак, общее решение будет иметь вид (числа Фибоначчи):

Пусть корни уравнения будут равные, то есть (корень кратный)

(7) и далее по аналогии.

Если имеется рекурсивное соотношение k-го порядка вида (1)

Если корни этого характеристического уравнения будут различны, то общее решение его будет:

Пример: Пусть этому корню кратности s в выражении (9) будет соответствовать своя сумма в выражении для общего решения уравнения