|
|
 |
Условие
Как будет выглядеть формула n-го члена для рекуррентной последовательности k-го порядка, если
a) характеристическое уравнение имеет простые корни
x1,..., xk, отличные от нуля;
б) характеристическое уравнение имеет отличные от нуля корни x1, ..., xm с кратностями α1, ..., αm соответственно?
Определения, связанные с рекуррентными последовательностями, смотри в
справочнике.
Решение
Пусть f(x) = βkxk + βk–1xk–1 + ... + β1x + β0 – многочлен. Для последовательности (a) = (a0, a1, a2, ...) через f(a) будем обозначать последовательность, n-й член которой равен βkan+k + βk–1an+k–1 + ... + β1an+1 + β0an. Если f – характеристический многочлен рекуррентной последовательности (a) k-го порядка, то f(a) = (0).
Легко проверить, что (αf)(a) = αf(a), (f + g)(a) = f(a) + g(a), (fg)(a) = f(g(a)).
Лемма. Если f = gh, где многочлены g и h взаимно просты, то f(a) = 0 тогда и только тогда, когда (a) = (b) + (c), где g(b) = 0 и h(с) = 0.
Доказательство. ⇐. f(a) = hg(b) + gh(c) = h(0) + g(0) = (0).
⇒. Согласно задаче 60990 найдутся такие многочлены u и v, что g(x)u(x) + h(x)v(x) = 1. Положим (b) = hv(a), (c) = gu(a), тогда
g(b) = vf(a) = 0, h(c) = vf(a) = 0, (a) = (b) + (c).
б) Достаточно найти общий вид рекуррентной последовательности (a) с характеристическим многочленом f(x) = (x – q)α, где q ≠ 0, а потом применить лемму.
Докажем, что an = g(n)qn, где g – произвольный многочлен степени не выше α – 1.
Пусть an = g(n)qn для всех n. Обозначим h(x) = x – q, тогда f = hα. Заметим, что n-й член последовательности h(a) равен
g(n + 1)qn+1 – qg(n)qn = Δg(n)qn+1. Поэтому n-й член последовательности f(a) равен Δαg(n)qn+α = 0, так как согласно задаче 61437 Δαg = 0.
Пусть f(a) = (0). Последовательность (a) полностью определяется начальными условиями a0, ..., aα–1. Поэтому достаточно подобрать такой многочлен g степени α – 1, что a0 = g(0), a1 = g(1)q, ..., aα–1 = g(α – 1)qα–1. Но такой многочлен существует (и единственен) – см. задачу 61052.
Ответ
а)
б) где gi – многочлен степени не выше αi – 1.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 11 |
| Название | Последовательности и ряды |
| Тема | Последовательности |
| параграф | |
| Номер | 2 |
| Название | Рекуррентные последовательности |
| Тема | Рекуррентные соотношения |
| задача | |
| Номер | 11.055 |
