Xreferat.com » Рефераты по математике » Возвратные последовательности

Возвратные последовательности

+ k = (1 + a1) Sn + k + (a2 - a1) Sn + k - 1 + . . . + (ak – ak - 1) Sn + 1 - akSn . (28)

Заметим, что

u1 = S1, u2 = S2 - u1 = S2 – S1, . . . , un = Sn – (u1 +. . .+ un - 1) = Sn - Sn – 1, (29)

Полагая S0 = 0 так, что u1 = S1 – S0, и подставляя в уравнение (26) вместо u1, u2, u3, . . . , un, . . . , их выражения через S0, S1, S2, . . . , Sn, . . . , получим:

Sn + k - Sn + k – 1 =a1(Sn + k – 1 - Sn + k – 2)+ a2(Sn + k – 2 - Sn + k – 3) + ... + ak(Sn - Sn – 1),

Откуда Sn + k = (1 + a1) Sn + k – 1 + (a2 - a1) Sn + k - 2 + . . . + (ak – ak - 1) Sn - akSn – 1 (n ≥ m),

или, заменяя здесь n через n+1:

Sn + k + 1 = (1 + a1) Sn + k + (a2 - a1) Sn + k - 1 + . . . + (ak – ak - 1) Sn + 1 - akSn         (n ≥ m - 1).

Это – возвратное уравнение порядка k + 1.

Примеры:

a)                Геометрическая прогрессия.

Здесь un = aqn-1 и

Sn = u1 + u2 + . . . + un = a + aq + . . . + aqn-1 .

Так как члены {un} удовлетворяют уравнению вида un + 1 = q un , то члены {Sn} должны удовлетворять уравнению

Sn (1 + q) Sn + 1 - q Sn .                                (30)

b)                Последовательность квадратов натуральных чисел.

Здесь un = n2 и Sn = 1 + 22 + . . . + n2 .

Так как члены {un} удовлетворяют уравнению

un + 3 = 3un + 2 - 3un + 1 + un ,

то члены {Sn} удовлетворяют уравнению вида

Sn + 4 = 4Sn + 3 - 6un + 2 + 4Sn + 1 - Sn .

c)                 Числа Фибоначчи.

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

un+2 = un+1 + un ,

то суммы их Sn должны удовлетворять уравнению

Sn+3 = 2Sn+2 - Sn .

§4. Формулы вычисления любого члена возвратной последовательности. Базис возвратного уравнения

В случае простейших возвратных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, а также периодической последовательности, можно находить любой член последовательности, не прибегая к вычислению предшествующих членов. Но в случае последовательности числе Фибоначчи или общей последовательности коэффициентов частного от деления двух многочленов, на первый взгляд это невозможно, и чтобы вычислить тринадцатое число Фибоначчи u13 , нужно найти предварительно, один за другим, все предшествующие члены (пользуясь уравнением un+2 = un+1 + un):

u1 = 1, u2 = 1, u3 = 2, u4 = 3, u5 = 5, u6 = 8, u7 = 13, u8 = 21, u9 = 34,

u10 = 55, u11 = 89, u12 = 144, u13 = 233.

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

un + k == a1un +k – 1 + a2un + k – 2 + … + akun                                                                     (31)

- возвратное уравнение порядка k. Если оно выполняется для всех натуральных значений n = 1, 2, 3, . . . , то, положив n = 1, получим:

uk + 1 == a1uk + a2uk – 1 + … + aku1 .

Теперь зная u1, u2, u3, . . . , uk можно вычислить uk + 1 . Полагая в уравнении (31) n = 2 найдём:

uk + 2 == a1uk + 1 + a2uk + … + aku2 .

Значит, уже известно и значение uk + 2 . Если m – какое-либо натуральное число, и уже вычислены члены последовательности u1, u2, u3, . . . , uk, uk + 1, . . . , um + k – 1, то, полагая в уравнении (31) n = m, найдём из него следующий член um + k.

Итак, члены возвратной последовательности порядка k, удовлетворяющей уравнению (31), определяются единственным образом с помощью этого уравнения, если известны первые k членов последовательности: u1, u2, u3, . . . , uk.

Выбирая их различными способами можно получить бесконечное множество различных последовательностей, удовлетворяющих уравнению (31). Их различие между собой будет проявляться уже в первых k членах и будет обнаруживаться также в дальнейших членах.

Так, например, уравнению первого порядка

un + 1 = qun

удовлетворяют всевозможные геометрические прогрессии со знаменателем q (они различаются друг от друга значениями первого члена u1).

Пусть имеем некоторое количество последовательностей, удовлетворяющих одному и тому же уравнению (31):

x1, x2, . . . , xn, . . . ,

y1, y2, . . . , yn, . . . ,

. . . . . . . . . . . . . . . .                                                                        (32)

z1, z2, . . . , zn, . . . ,

Тогда выполняется уравнение:

xn + k == a1xn +k – 1 + a2xn + k – 2 + … + akxn ,

yn + k == a1yn +k – 1 + a2yn + k – 2 + … + akyn ,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                 (33)

zn + k == a1zn +k – 1 + a2zn + k – 2 + … + akzn ,

Возьмём произвольные числа A, B, . . . , C, по числу последовательностей (32), умножим все члены первого из уравнений на А, второго на В, . . . , последнего на С и сложим . Тогда получится равенство:

А xn + k + В yn + k + . . . + С zn + k =

= a1(Аxn +k – 1 + Вyn +k – 1 + . . . + Czn +k – 1) +

+a2(Аxn +k – 2 + Вyn +k – 2 + . . . + Czn +k – 2) + ... + ak(Аxn + Вyn + ... + Czn).(34)

Из него следует, что последовательность

t1 = Аx1 + Вy1 + . . . + Cz1,

t2 = Аx2 + Вy2 + . . . + Cz2,

. . . . . . . . . . . . . . . . . . . . .                                                               (35)

tn = Аxn + Вyn + . . . + Czn,

. . . . . . . . . . . . . . . . . . . . .

Получающаяся из последовательностей (32) путём умножения всех членов первой из них на А, второй на В, . . . , последней на С и затем почленного сложения последовательностей, удовлетворяет уравнению (31). Изменяя A, B, . . . , C, можно получить различные значения членов t1, t2, t3, ...

Пусть

u1, u2, u3, . . . , un, . . . ,                                                                    (36)

- какая-либо последовательность, удовлетворяющая уравнению (31). Если удастся придать числам A, B, . . . , C такие значения, чтобы первые k членов последовательности (35) совпали бы с первыми k членами последовательности (36), то совпадут и все члены последовательностей (35) и (36), т. е. при любом натуральном n будем иметь:

un = Аxn + Вyn + . . . + Czn.                                                              (37)

Таким образом, открывается возможность представить любую из бесконечного множества последовательностей, удовлетворяющих одному и тому же возвратному уравнению порядка k, через некоторые из них (32), по формуле (37).

Реализация этой возможности зависит от того, возможно ли подобрать числа A, B, . . . , C так, чтобы удовлетворялись уравнения:

Аx1 + Вy1 + . . . + Cz1 = u1

Аx2 + Вy2 + . . . + Cz2 = u2

. . . . . . . . . . . . . . . . . . . . .                                                               (38)

Аxk + Вyk + . . . + Czk = uk

с произвольно заданными значениями правых частей u1, u2, u3, . . . , uk.

Так как неизвестными здесь являются числа A, B, . . . , C, а число уравнений равно порядку k возвратного уравнения, то отсюда следует, что и количество неизвестных A, B, . . . , C целесообразно взять также равным k. Известно, что наличие решений у системы k алгебраических уравнений (38) с k неизвестными A, B, . . . ,

C зависит от того, каковы коэффициенты этой системы: x1, y1, . . . , z1, . . . , xk, yk, . . . ,zk, т. е. от того, каковы начальные члены последовательностей (32).

Решение будет существовать при произвольных правых частях u1, u2, u3, . . . , uk, если положим

x1 = 0, y1 = 0, . . . , z1 = 0

x2 = 0, y2 = 0, . . . , z2 = 0

. . . . . . . . . . . . . . . . . . . .                                                                 (39)

xk = 0, yk = 0, . . . , zk = 1

В этом случае система (38) принимает простейший вид, сразу обнаруживающий решение системы

А = u1

В = u2

. . . . . .

C = uk

Возможен иной выбор чисел x1, y1, . . . , z1, . . . , xk, yk, . . . ,zk, при котором система (38) имеет решение, каковы бы ни были правые части уравнений.

ТЕОРЕМА. Для того чтобы система k линейных алгебраических уравнений (38) с k неизвестными имела решение A, B, . . . , C и притом единственное, при любых значениях правых частей u1, u2, u3, . . . , uk, необходимо и достаточно, чтобы соответствующая ей однородная система

Аx1 + Вy1 + . . . + Cz1 = 0

Аx2 + Вy2 + . . . + Cz2 = 0

. . . . . . . . . . . . . . . . . . . . .                                                               (38')

Аxk + Вyk + . . . + Czk = 0

имела бы одно только нулевое решение:

A = B = . . . = C = 0.

Если числа такого рода выбраны в качестве начальных членов последовательностей (32), то любая последовательность, удовлетворяющая возвратному уравнению (31), выразится по формуле (37), где числа A, B, . . . , C определяются из уравнений (38). Система k последовательностей (32), через которые члены любой последовательности, удовлетворяющей данному уравнению (31), выражаются по формулам (37), называется базисом возвратного уравнения.

Вывод: для каждого возвратного уравнения порядка k существует бесконечное множество различных, удовлетворяющих ему последовательностей. Любую из них можно составить из k последовательностей, удовлетворяющих этому уравнению и образующих его базис, путём умножения каждой из k последовательностей соответственно на некоторые числа A, B, . . . , C и почленного сложения.

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

§5. Характеристическое уравнение для возвратного уравнения

Покажем, что при некоторых условиях можно найти базис возвратного уравнения (31)

un + k == a1un +k – 1 + a2un + k – 2 + … + akun ,

состоящий из k геометрических прогрессий с различными знаменателями. Выясним, при каких условиях некоторая геометрическая прогрессия

x1 = 1, x2 = q, . . . , xn = qn – 1, . . . ,            (q ≠ 0)

удовлетворяет уравнению (31). Замечая, что

xn + k = qn + k – 1, xn + k - 1 = qn + k – 2, . . . , xn = qn – 1

и подставляя эти величины в уравнение (31) получим:

qn + k – 1 = a1 qn + k – 2+ a2 qn + k – 3 + … + an qn – 1,

откуда qk = a1 qk – 1+ a2 qk – 2 + … + ak .                                          (40)

Итак, геометрическая прогрессия только тогда может удовлетворять возвратному уравнению (31) порядка k, когда знаменатель прогрессии q удовлетворяет алгебраическому уравнению (40) степени k с теми же коэффициентами, как и в уравнении (31). Уравнение (40) называется характеристическим для возвратного уравнения (31).

Вывод: возвратному уравнению порядка k соответствует алгебраическое уравнение степени k с теми же коэффициентами – его характеристическое уравнение. Каждый из корней характеристического уравнения представляет знаменатель геометрической прогрессии, удовлетворяющий данному возвратному уравнению. В случае, когда все корни характеристического уравнения различны между собой, получаются k различных геометрических прогрессий, образующих базис возвратного уравнения. Следовательно, в этом случае члены любой последовательности, удовлетворяющей возвратному уравнению, можно получить путём почленного сложения некоторых геометрических прогрессий (числом k).

При решении некоторых возвратных задач иногда используют следующую теорему.

ТЕОРЕМА. Пусть a и b – два натуральных числа, причём a < b; тогда число операций последовательного деления в алгоритме Евклида, необходимых для отыскания наибольшего общего делителя a и b, не превосходит упятерённого числа цифр числа а, записанного по десятичной системе счисления.

§6. Возвратные задачи

1. Задача о ханойской башне

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: