Постоянными коэффициентами

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

f(n + k) = a₁×f(n + k – 1) + … + a_k×f(n).

Теорема. Следующие условия для последовательности {u_n} комплексных чисел эквивалентны:

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

f(n + k) = a₁×f(n + k – 1) +… + a_k×f(n).

(2) u_n = , где l₁ , … , l_s – различные корни характеристического уравнения c(l) = 0 кратностей r₁ , … , r_s соответственно, где c(l) = l^k – a₁×l^k–1 –…– a_k–1×l – a_k – характеристический многочлен, (это значит, что l^k – a₁×l^k–1 – … – a_k–1×l – a_k = (l – l₁) ×…×(l – l_s) ), а P_i(x) – некоторый многочлен, степень которого меньше соответствующей кратности r_i (1 £ i £ s).

Доказательство. (1) Þ (2) Если u_n+k = a₁×u_n+k–1 +…+ a_k×u_n (n Î N₀), то умножая каждое из этих равенств на xⁿ и складывая, получим:

u_k×x⁰ + u_k+1×x¹+… = a₁×( u_k–1×x⁰ + u_k×x¹+…)+…+a_k×(u₀×x⁰+u₁×x¹+ …) Û

Û u(x)×(1–a₁×x–a₂×x²– … –a_k–1×x^k–1–a_k×x^k) =

= (u₀+u₁×x+…+u_k–1×x^k–1) – a₁×x×(u₀+u₁×x+…+u_k–2×x^k–2)– … – a_k–1×x^k–1×u₀ .

В правой части этого равенства стоит многочлен

P(x) = (u₀+u₁×x+…+u_k–1×x^k–1) – a₁×x×(u₀+u₁×x+…+u_k–2×x^k–2)– … – a_k–1×x^k–1×u₀

степени не выше k–1, так что u(x) = , что и требовалось.

(2) Þ (3) Пусть u(x) = , где P(x) – многочлен степени не выше k–1. Разложим многочлен x^k – a₁×x^k–1 – … – a_k–1×x – a_k в произведение линейных множителей над алгебраически замкнутым полем C:

x^k – a₁×x^k–1 – … – a_k–1×x – a_k = (x – l₁) ×…×(x – l_s) ,

где l₁ , … , l_s – попарно различные корни кратностей r₁ , … , r_s .

Ясно, что 1 – a₁×x – … – a_k×x^k =

=

= (1 – l₁×x) × … ×(1 – l_s×x) .

Поэтому производящую функцию u(x) можно представить в виде

u(x) =

разложения в сумму простых дробей, где b_ij Î C (1 £ i £ s, 1 £ j £ r_i). Здесь важно учитывать, что степень числителя P(x) меньше степени знаменателя. Воспользовавшись разложениями в ряд

, получим

u(x) =

По определению производящей функции, коэффициент при степенях переменной x равен соответствующему члену последовательности.

Значит, (k Î N₀). При этом участвующую здесь сумму можно рассматривать как многочлен от k, степень каждого из выделенных слагаемых в котором не превосходит j–1 , в целом степень многочлена не превосходит r_i – 1. Обозначая этот многочлен через P_i(x), получим: , что и требовалось.

(3) Þ (1) Пусть теперь , где степень многочлена P_i(x) не превосходит r_i – 1, т.е. .

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

Ввиду линейной структуры решений этого соотношения достаточно проверить, что решениями будут все произведения вида k^j×l_i^k , где 0 £ j < r_i . Это значит, что выполнены следующие соотношения:

(n+k)^j×l^n+k = a₁×(n+k–1)^j×l^n+k–1+…+a_k×n^j×lⁿ , l = l_i , n Î N₀ .

Если l = 0 – корень многочлена c(x) = x^k – a₁×x^k–1 –…– a_k–1×x – a_k , то a_k = 0, и соотношения выполняются.

Они будут выполнены и в случае j = 0, т.к. l^k = a₁×l^k–1 + …+ a_k–1×l + a_k .

В случае j ³ 1 воспользуемся формулой бинома Ньютона

:

(n+k)^j×l^n+k = a₁×(n+k–1)^j×l^n+k–1+…+a_k×n^j×lⁿ Û

Û (n+k)^j×l^k = a₁×(n+k–1)^j×l^k–1+…+a_k–1×(n+1)^j×l+a_k×n^j Û

Û .

Докажем, что совпадают коэффициенты при всех степенях n, т.е.

l^k = a₁×l^k–1 + … + a_k–1×l + a_k (для n^j),

Û

Û l^k–1×kⁱ = a₁×l^k–2×(k–1)ⁱ+…+a_k–2×l×2ⁱ+a_k–1 (для n^j–i , i > 0).

Это следует из приводимой ниже леммы.

Теорема доказана.

Лемма (соотношения для r-кратного корня многочлена). Если l – корень кратности r > 0 многочлена f(x) = x^k – a₁×x^k–1 – … – a_k–1×x – a_k , то справедливы соотношения

l^k = a₁×l^k–1 + … + a_k–1×l + a_k ,

l^k–1×kⁱ = a₁×l^k–2×(k–1)ⁱ+…+a_k–2×l×2ⁱ+a_k–1 (1 £ i < r).

При этом l^k–1×k^r ¹ a₁×l^k–2×(k–1)^r+…+a_k–2×l×2^r+a_k–1 .

Доказательство. Проведём индукцию по степени многочлена. Для многочлена первой степени нужно доказать только первое из соотношений, которое следует и в общем случае из условия леммы (l – корень многочлена). При этом очевидно, что указанное в формулировке леммы неравенство тоже выполнено. Столь же просто рассматривается и случай k = 2.

Предположим, что лемма доказана для многочленов степени меньше k и докажем её для многочлена степени k. Поскольку l – корень кратности r–1 для производной многочлена f¢(x) = k×x^k–1 – a₁×(k–1)×x^k–2 – … – a_k–2×2×x – a_k–1 степени k–1, то запишем соответствующие соотношения для многочлена :

(1 £ i < r – 1), которые можно записать так:

l^k–1×k = a₁×l^k–2×(k–1)+…+a_k–2×l×2+a_k–1 ,

l^k–2×(k–1)ⁱ×k = a₁×l^k–3×(k–2)ⁱ×(k–1)+a₂×l^k–4×(k–3)ⁱ×(k–2)+…+a_k–3×l×3×2ⁱ+a_k–2×2

(1 £ i < r–1).

Первое из этих равенств даёт искомое соотношение при i = 1 для исходного многочлена, а из второй группы равенств получаем:

l^k–1×k²–l^k–1×k = a₁×l^k–2×(k–2)×(k–1)+a₂×l^k–3×(k–3)×(k–2)+…+a_k–3×l²×3×2+a_k–2×2×l ,

l^k–1×k² = (a₁×l^k–2×(k–2)×(k–1)+a₂×l^k–3×(k–3)×(k–2)+…+a_k–3×l²×3×2+a_k–2×2×l)+

+(a₁×l^k–2×(k–1)+a₂×l^k–3×(k–2)+…+a_k–3×l²×3+a_k–2×l×2+a_k–1) =

= a₁×l^k–2×(k–1)²+ a₂×l^k–3×(k–2)²+…+ a_k–3×l²×3²+ a_k–2×l×2²+a_k–1 .

Это – доказываемое соотношение для исходного многочлена при i = 2. Если эти соотношения уже доказаны при i = 1, 2, … , s < r и s+1 < r, то s < r+1 и можно воспользоваться s-м из доказанных соотношений:

l^k–1×(k–1)^s×k = a₁×l^k–2×(k–2)^s×(k–1)+a₂×l^k–3×(k–3)^s×(k–2)+…+a_k–3×l²×3×2^s+a_k–2×2×l Û

Если предположить, что l^k–1×k^r = a₁×l^k–2×(k–1)^r+…+a_k–2×l×2^r+a_k–1 , то приведённые выше преобразования, пройденные в обратном порядке, приведут к соотношению

l^k–1×(k–1)^r–1×k=a₁×l^k–2×(k–2)^r–1×(k–1)+a₂×l^k–3×(k–3)^r–1×(k–2)+…+a_k–3×l²×3×2^r–1+a_k–2×2×l Û

Это противоречит предположению индукции для многочлена .

Лемма доказана.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: