§ 2. Метод производящих функций для нахождения общего решения линейного однородного рекуррентного соотношения второго порядка

Продемонстрируем общий метод решения линейных однородных соотношений с постоянными коэффициентами на примере соотношения второго порядка. Использованный для нахождения формулы членов общего решения этого рекуррентного соотношения метод производящих функций будет в дальнейшем применён и в общем случае.

Для последовательности {u_n} введём в рассмотрение формальный степенной ряд u(x) = , называемый производящей функцией последовательности {u_n} . Ясно, что этот ряд хранит всю информацию об исходной последовательности.

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

Рассмотрим линейное однородное рекуррентное соотношение с постоянными коэффициентами f(n + 2) = a₁f(n + 1) + a₂f(n), где a₂  0 (иначе соотношение будет первого порядка).

Любое его решение {u_n} удовлетворяет соотношениям:

u₂ = a₁u₁ + a₂u₀ |  x⁰

u₃ = a₁u₂ + a₂u₁ |  x¹

. . .

u_i+2 = a₁u_i+1 + a₂u_i |  xⁱ

. . .

Умножая эти равенства на xⁱ и складывая, получим

u₂x⁰ + u₃x¹ + … + u_i+2xⁱ + … = a₁(u₁x⁰ + u₂x¹ + … + u_i+1xⁱ + … ) +

+ a₂(u₀x⁰ + u₁x¹ + … + u_ixⁱ + … ),

которое эквивалентно системе написанных выше равенств: эти равенства немедленно получаются, если приравнять коэффициенты при одинаковых степенях переменной x в этих рядах. Далее,

u₂x⁰ + u₃x¹+u₄x² + … = a₁( u₁x⁰ + u₂x¹+u₃x²+…)+a₂(u₀x⁰+u₁x¹+ …) 

 u(x) – u₀ – u₁x = a₁x(u(x) – u₀) +a₂x²u(x) 

 u(x)(1 – a₁x – a₂x²) = u₀ + u₁x – u₀a₁x,

т.е. .

Рассмотрим характеристическое уравнение (x) = x² – a₁x – a₂ = 0, которое всегда имеет корни в поле комплексных чисел C . При этом (x) = x² – a₁x – a₂ = (x – ₁)(x – ₂). Теперь 1 – a₁x – a₂x² = = = (1–₁x)(1 – ₂x), так что

,

где U₀ = u₀ , U₁ = u₁ – a₁u₀ .

Оказывается, что эту дробь можно разложить в сумму элементарных дробей. Под этим понимается разложение вида в случае ₁  ₂ и разложение при ₁ =  = ₂ .

В этом легко убедиться непосредственно, найдя числа A и B. В первом случае, умножив на общий знаменатель (1 – ₁x)(1 – ₂x), получим равенство U₀ + U₁x = A(1 – ₂x) + B(1 – ₁x). Приравнивая коэффициенты при одинаковых степенях x, приходим к системе уравнений относительно A и B, из которой находим .

Во втором случае кратного корня аналогично получаем:

U₀ + U₁x = A(1 – x) + B  .

Здесь   0, поскольку иначе a₂ = ₁₂ = 0 – противоречие.

Рассмотрим теперь два случая:

1. ₁  ₂ . Тогда , и для разложения в ряд можно применить легко доказываемую формулу = 1 + y + y² + … :

= 1 + y + y² + …  (1 – y)(1 + y + y² + …) = 1 

 (1 + y + y² + … ) – y – y² – y³ – … = 1,

что верно.

Таким образом, в случае различных корней получим

.

Вспоминая определение производящей функции, получаем u_n = A₁ⁿ + B₂ⁿ , где A и B – некоторые комплексные постоянные.

2. ₁ =  = ₂ . Тогда . Для получения разложения в ряд второй дроби продифференцируем разложение = 1 + y + y² + … :

.

Таким образом,

Поэтому u_n = ((A+B) + Bn)ⁿ , для некоторых констант A, B  C .

Проверим теперь, что последовательности u_n = c₁₁ⁿ + c₂₂ⁿ (в случае ₁  ₂) и u_n = (c₁ + с₂n)ⁿ (для случая ₁ =  = ₂) с произвольными постоянными c₁ , c₂  C будут решениями линейного однородного рекуррентного соотношения f(n+2) = a₁f(n+1) + a₂f(n) второго порядка.

В первом случае: f(n+2) – a₁f(n+1) + a₂f(n) =

= c₁₁ⁿ⁺² + c₂₂ⁿ⁺² – a₁(c₁₁ⁿ⁺¹ + c₂₂ⁿ⁺¹) – a₂( c₁₁ⁿ + c₂₂ⁿ) =

= c₁₁ⁿ(₁² – a₁₁ – a₂) + c₂₂ⁿ(₂² – a₁₂ – a₂) = 0 + 0 = 0,

т.к. ₁ и ₂ – корни уравнения ² – a₁ – a₂ .

Во втором случае f(n+2) – a₁f(n+1) + a₂f(n) =

= (с₁ + с₂(n+2))ⁿ⁺² – a₁(с₁ + с₂(n+1)) ⁿ⁺¹ – a₂(с₁ + с₂n) ⁿ =

= c₁ⁿ(² – a₁ – a₂) + c₂ⁿ((n+2)² – a₁(n+1) – a₂n) =

= c₁ⁿ0 + c₂ⁿ[n(² – a₁ – a₂) +2² – a₁] = c₂ⁿ[n0 + 0] = 0,

т.к. ² – a₁ – a₂ = 0 и x² – a₁x – a₂ = (x – )(x – ), т.е. a₁ = 2 .

Итак, доказана

Теорема (об общем решении линейного однородного рекуррентного соотношения с постоянными коэффициентами). Следующие условия для последовательности {u_n} комплексных чисел эквивалентны:

(1) последовательность {u_n} является решением линейного однородного рекуррентного соотношения с постоянными коэффициентами

f(n + 2) = a₁f(n + 1) + a₂f(n).

(2) если характеристическое уравнение () = 0, где () = ² – a₁ – a₂ , имеет два различных корня ₁ и ₂ , то u_n = ₁ⁿc₁ + ₂ⁿc₂ (c₁ , c₂  C);

если характеристическое уравнение () = 0, где () = ² – a₁ – a₂ , имеет два совпавших корня ₁ =  = ₂ , то u_n = ⁿ(c₁ + c₂n) (c₁ , c₂  C).

Эта теорема даёт метод нахождения общего решения произвольного однородного линейного рекуррентного соотношения с постоянными коэффициентами: