коэффициентами и специальной правой частью

Теорема (о частном решении линейного неоднородного рекуррентного соотношения). Для любого линейного рекуррентного соотношения с постоянными коэффициентами

f(n + k) = a₁×f(n + k – 1) + …+ a_k×f(n) + T_m(n)×lⁿ,

где T_m(x) – многочлен степени m, l Î С, существует решение вида n^r×S_m(n)×lⁿ , где S_m(x) – некоторый многочлен степени m, а r – кратность корня l в характеристическом уравнении x^k – a₁×x^k–1 – … – a_k–1×x – a_k = 0 . В частности, если l не является корнем характеристического уравнения, то нужно считать r = 0.

Доказательство. Подставим n^r×(s_m×n^m+…+s₁×n+s₀)×lⁿ в рекуррентное соотношение:

(здесь всегда можно считать m > r, используя, если необходимо, нулевые коэффициенты многочленов).

В случае, когда l не является корнем характеристического многочлена, т.е. r = 0, система упрощается:

Видно, что система имеет верхнетреугольный вид с диагональными элементами c(l) ¹ 0, а потому имеет единственное решение.

Если же l – это r-кратный корень характеристического многочлена c(x), то в силу леммы о соотношениях для r-кратного корня многочлена последняя группа уравнений системы тривиальна: все коэффициенты в ней нулевые. Действительно, эти коэффициенты имеют вид , где u = m+j–r (j = 1, … , r).

При этом

по упомянутой выше лемме.

Более того, система снова верхнетреугольная. В самом деле, если j > u, токоэффициент при s_u в j-м уравнении первой группы (j £ r) равен

по лемме о соотношениях для r-кратного корня многочлена, т.к. u+r–j < r при j > u. При j = u коэффициент при s_u равен

и отличен от нуля по той же лемме.

Если же j > r, то коэффициенты могут быть ненулевыми только для значений u из диапазона j–r £ u £ m. При этом

по лемме о соотношениях для r-кратного корня многочлена, т.к. u+r–j < r при j > u. При j = u > r коэффициент при s_u равен и отличен от нуля по той же лемме.

Таким образом, в любом случае полученная система уравнений крамерова и имеет единственное решение.

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

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

Пример. 1.Найти формулу общего члена решения рекуррентного соотношения f(n + 3) = f(n) + 1.

Здесь c(x) = x³ – 1 имеет три простых корня l₁ = 1, , а свободный член соотношения представим в виде 1 = l₁ⁿ×T₀(x), где T₀(x) = 1. Таким образом, общее решение однородного соотношения записывается в виде c₁×l₁ⁿ + c₂×l₂ⁿ + c₃×l₃ⁿ, а частное решение неоднородного соотношения – в виде c×n×l₁ⁿ = c×n. Подставляя это выражение в исходное соотношение, получаем соотношение с×(n+3) = c×n + 1, откуда находим c = .

Таким образом, общее решение рассматриваемого неоднородного соотношения имеет вид c₁×l₁ⁿ + c₂×l₂ⁿ + c₃×l₃ⁿ + .

2. Найти формулу общего члена решения рекуррентного соотношения

f(n + 1) = f(n) + n² – 1.

Здесь c(l) = l – 1 имеет единственный корень l = 1, так что общее решение однородного соотношения j(n, c) = c.

Частное решение неоднородного соотношения будем искать в виде n·(s₂×n²+s₁×n+s₀)×1ⁿ, т.к. свободный член рассматриваемого соотношения имеет вид 1ⁿ×T₂(n), где T₂(x) = x² – 1. Подставляя это выражение в исходное соотношение, получим

s₂×(n + 1)³+s₁×(n + 1)²+s₀×(n + 1) = s₂×n³ + s₁×n² + s₀×n + n² – 1,

т.е. 3×s₂×n²+(3×s₂ + 2×s₁)×n + s₂ + s₁+s₀ = n² – 1, откуда , а значит, s₂ = , s₁ = – , s₀ = – . Таким образом, общее решение рассматриваемого неоднородного соотношения имеет вид

w(n) = с + ( ×n³ – ×n² – ×n).

Некоторые примеры применения

Производящих функций

I. Вычисление частичных сумм последовательностей. Пусть задана последовательность {u_n} с производящей функцией u(x) = . Найдём производящую функцию s(x) последовательности {s_n} её частичных сумм, где s_n = u₀ + … + u_n .

Имеем s(x) = s₀ + s₁×x + s₂×x² +… = u₀ + (u₀+u₁)×x + (u₀ + u₁ + u₂)×x² +… = = u₀ + u₁×x + u₂×x² + … + u₀×x + (u₀ + u₁)×x² +… = u(x) + s(x)×x. Отсюда получаем (1 – x)×s(x) = u(x), и окончательно s(x) = .

Знание производящей функции, как было показано ранее, позволяет находить формулы для членов последовательностей. Таким образом, открывается путь для задания формулами частичных сумм последовательностей.

Пример. Пусть u_n = n (n Î N₀). Тогда u(x) = =

.

Поэтому s(x) = . Если учесть, что

(1 – y) ^–r = 1+r×y+ ·y² + … = ,

то полученная формула записывается в виде ряда

.

Таким образом, s_n = , т.е. 1+2+…+n = .

2. Доказательство некоторых тождеств. Рассмотрим известную формулу бинома Ньютона: . Сумму в правой части можно рассматривать как производящую функцию последовательности , где для i £ n, и при i > n. Тогда, с одной стороны,

,

а с другой – справедливо равенство

Сравнивая коэффициенты при одинаковых степенях x в полученных формулах, приходим к соотношению , в котором, как и выше, считается, что при i > n.

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

Л И Т Е Р А Т У Р А

1.Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.

2.Асеев. Дискретная математика: Учеб. пособие – Ростов н / Д.: Феникс, 2003.

3.Виленкин Н.Я. Элементы комбинаторики. – М.: Наука, 1969.

4.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. Учеб. пособие. – М.: Физматлит, 2004.

5.Журавлёв Ю.И. и др. Сборник задач по дискретному анализу. Комбинаторика. Элементы алгебры и логики. Теория графов. – М.: МФТИ-рио, 2004.

6.Зыков А.А. Основы теории графов: Учебник. – М.: Вузовская книга, 2004.

7.Матросов В.Л., Стеценко В.А. Лекции по дискретной математике. – М.: МПГУ, 1997.

8.Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2002.

9.Редькин Н.П. Дискретная математика. – СПб.: Издательство “Лань”, 2006.

10.Холл М. Комбинаторика. – М.: Мир, 1970.

11.Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 2006.

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