Курсовая работа: Возвратные последовательности

Здесь u₁ = 5, u₂ = 7, u₃ = 1, u₄ = 3, u₅ = 2, u₆ = 1, u₇ = 3, . . . , (14)

Очевидно, что u_{n + 3} = u_n (n ≥ 3). (15)

Чтобы представить это уравнение в виде (2), перепишем его следующим образом:

u_{n + 3} = 0•u_{n + 2} + 0•u_{n + 1} + 1•u_n .

Отсюда видно, что это возвратное уравнение третьего порядка ( k = 1, a₁ = 0, a₂ = 0, a₃ = 0). Значит последовательность (14) является возвратной последовательностью третьего порядка.

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

P (x) = A₀ + A₁ x + . . . + A_l x^l

Q (x) = B₀ + B₁ x + . . . + B_k x^k (B₀ ≠ 0).

Будем делить P (x) на Q (x). Если P (x) не делится на Q (x) без остатка, то деление можно продолжать неограниченно. В частном один за другим будут получаться члены:

D₀ + D₁ x + D₂ x² + D₃ x³ + . . . + D_n xⁿ + . . .

Рассмотрим последовательность

u₁ = D₀ , u₂ = D₁ , . . . , u_n = D_{n - 1} , . . . (16)

и докажем, что она является возвратной порядка k ( k – степень делителя). Фиксируем произвольное натуральное число n, удовлетворяющее единственному условию n ≥ l – k + 1, и остановимся в процессе деления на члене частного, содержащем x^{n + k} . Тогда в остатке получится некоторый многочлен R (x), содержащий x в степенях выше, чем n + k. Записывая соотношение между делимым, делителем, частным и остатком, получим следующее тождество:

A₀ +A₁ x+…+A_l x^l =(B₀ +B₁ x+...+B_k x^k )•(D₀ +D₁ x+D₂ x² +D₃ x³ +...+D_n+k x^n+k )+R(x)

Найдём коэффициенты при x^{n + k} в левой и правой частях этого тождества и приравняем их между собой. Так как n + k ≥ l + 1, то коэффициент при x^{n + k} в левой части равен нулю. Поэтому должен равняться нулю и коэффициент при x^{n + k} в правой части. Но члены с x^{n + k} содержатся здесь только в произведении

( B₀ + B₁ x + . . . + B_k x^k ) • ( D₀ + D₁ x + D₂ x² + D₃ x³ + . . . + D_{n + k} x^{n + k} )

(остаток R (x) содержит x в более высоких степенях). Поэтому искомый коэффициент есть

D_{n + k} B₀ + D_{n + k - 1} B₁ + . . . + D_n B_k . (17)

По предыдущему он должен равняться нулю:

D_{n + k} B₀ + D_{n + k - 1} B₁ + . . . + D_n B_k = 0, откуда (B₀ ≠ 0)

D_{n + k} = - D_{n + k – 1} - . . . - D_n (n ≥ l – k + 1). (18)

Это возвратное уравнение порядка k, откуда следует. Что последовательность (16) есть возвратная последовательность порядка k.

§2. Обобщение произвольных возвратных последовательностей

Из всех рассмотренных примеров наиболее общий характер имеет пример 6. Покажем, что произвольная возвратная последовательность порядка k

u₁ , u₂ , u₃ , . . . , u_n , . . . , (19)

удовлетворяющая уравнению вида

u_{n + k} = a₁ u_{n +k – 1} + a₂ u_{n + k – 2} + … + a_k u_n (nm 1), (20)

совпадает с последовательностью коэффициентов частного, полученного от деления многочлена P (x) на многочлен

Q (x) = 1 - a₁ x - . . . - a_k x^k . (21)

Пусть n – произвольное натуральное число, удовлетворяющее условию n > k + m – 2; умножим многочлен Q (x) на u₁ + u₂ x + u₃ x² + . . . +u_{n + 1} xⁿ . Получим: