Зворотні послідовності

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти Республіки Білорусь
Установа освіти
«Білоруський державний педагогічний університет
імені Максима Танка »
Математичний факультет
Кафедра алгебри та аналітичної геометрії
Курсова робота
Зворотні послідовності
Виконала студентка 4 курсу
математичного факультету, гр. 405
Волісова Олена Валеріївна
Керівник:
кандидат фіз.-мат. наук, доцент
Барковіч Оксана Аркадіївна
Мінськ 2009

Зміст
"1-3" Вступ
Глава 1 (теоретична частина)
§ 1. Визначення поворотної послідовності
§ 2. Узагальнення довільних зворотних послідовностей
§ 3. Вивчення і застосування зворотних послідовностей в курсі середньої школи
§ 4. Формули обчислення будь-якого члена поворотної послідовності. Базис поворотного рівняння
§ 5. Характеристичне рівняння для поворотного рівняння
§ 6. Зворотні задачі
Глава 2 (практична частина)
Висновок
Список літератури

Введення
Поняття поворотної послідовності є широким узагальненням поняття арифметичної і геометричної прогресії. Як окремі випадки воно охоплює також послідовності квадратів або кубів натуральних чисел, послідовності цифр десяткового розкладання раціонального числа (і взагалі будь-які періодичні послідовності), послідовності коефіцієнтів приватного від ділення двох многочленів, розташованих по зростаючим ступенями x, і т.д. Теорія зворотних послідовностей складає особливу главу математичної дисципліни, званої обчисленням кінцевих різниць.
Тема «Поворотні послідовності» не є ізольованою, ніде не використовуваної теорією. Навпаки, поворотні послідовності близькі до шкільного курсу математики, використовуються найвищою алгебри, геометрії, математичному аналізі та інших математичних дисциплінах.
Таким чином, поворотні послідовності є справжньою маленькою теорією, закінченою, простий, ясною.
Метою даної курсової роботи є вивчення теорії зворотних послідовностей і можливе застосування її частини на факультативах в шкільному курсі математики.
У цій роботі також розглянуті поворотні завдання. В основі рішення зворотних задач лежить ідея повернення (або рекурентності), згідно з якою рішення всієї задачі залежить від рішення того ж самого завдання менших розмірів.

Глава 1 (теоретична частина)

§ 1. Визначення поворотної послідовності

Будемо записувати послідовності у вигляді
u 1, u 2, u 3,. . . , U n,. . . , (1)
або, коротко, {u n}. Якщо існує натуральне число k і числа a 1, a 2, ..., a k ​​(справжні чи уявні), такі, що, починаючи з деякого номера n і для всіх наступних номерів,
u n + k == a 1 u n + k - 1 + a 2 u n + k - 2 + ... + a k u n (n m 1), (2)
то послідовність (1) називається поворотної послідовністю порядку k, а співвідношення (2) - поворотним рівнянням порядку k.
Таким чином, поворотна послідовність характеризується тим, що кожен її член (починаючи з деякого з них) виражається через одне і те ж кількість k безпосередньо передують йому членів за формулою (2).
Сама назва «поворотна» (а також рекурентна, від французького recurrente - повертаючись до початку) вживається саме тому, що тут для обчислення подальшого члена повертаються до попередніх членів.
Приклад 1. Геометрична прогресія. Нехай маємо геометричну прогресію:
u 1 = a, u 2 = aq, u 3 = aq 2,. . . , U n = aq n - 1,. . . , (3)
для неї рівняння (2) набуває вигляду:
u n + 1 = qu n. (4)
Тут k = 1 і a 1 = q. Таким чином, геометрична прогресія є поворотною послідовністю першого порядку.
Приклад 2. Арифметична прогресія. У разі арифметичній прогресії
u 1 = a, u 2 = a + d, u 3 = a + 2d,. . . , U n = a + (n - 1) d,. . . ,
маємо: u n + 1 = u n + D
- Співвідношення, яке не має виду рівняння (2). Але якщо розглянути два співвідношення, написані для двох сусідніх значень n:
u n + 2 = u n + 1 + d і u n + 1 = u n + d,
то отримаємо з них, шляхом почленного вирахування:
u n + 2 - u n + 1 = u n + 1 - u n,
або u n + 2 = 2u n + 1 - u n (5)
- Рівняння виду (2). Тут k = 2, a 1 = 2, a 2 = -1. Отже, арифметична прогресія є поворотною послідовністю другого порядку.
Приклад 3. Розглянемо старовинну завдання Фібоначчі про кількість кроликів. У ній потрібно визначити число пар зрілих кроликів, що утворилися від однієї пари протягом року, якщо відомо, що кожна зріла пара кроликів щомісячно народжує нову пару, причому новонароджені досягають статевої зрілості протягом місяця. У цьому завданні цікавий не результат, а послідовність, члени якої висловлюють спільне число зрілих пар кроликів в початковий момент (u 1), через місяць (u 2), через два місяці (u 3), і через n місяців (u n +1 ). Очевидно, що u 1 = 1. Через місяць додасться пара новонароджених, але число зрілих пар буде видно: u 2 = 1. Через два місяці кроленята досягнуть зрілості, і загальне число зрілих пар буде дорівнює двом: u 3 = 2.
Нехай вирахували вже кількість зрілих пар через n - 1 місяців - u n і через n місяців - u n +1. Так як до цього часу u n раніше наявних зрілих пар дадуть ще u n пар приплоду, то через n + 1 місяців загальне число зрілих пар буде:
u n +2 = u n +1 + u n.                                                                                                                                     (6)
Звідси u 4 = u 3 + u 2 = 3, u 5 = u 4 + u 3 = 5, u 6 = u 5 + u 4 = 8, u 7 = u 6 + u 5 = 13, ...
Таким чином, отримали послідовність
u 1 = 1, u 2 = 1, u 3 = 2, u 4 = 3, u 5 = 5, u 6 = 8, u 7 = 13,. . . , (7)
в якій кожен наступний член дорівнює сумі двох попередніх. Ця послідовність називається послідовністю Фібоначчі, а її члени - числами Фібоначчі.
Приклад 4. Розглянемо послідовність квадратів натуральних чисел:
u 1 = 1 2, u 2 = 2 2, u 3 = 3 2,. . . , U n = N 2,. . . (8)
Тут u n + 1 = (n + 1) 2 = n 2 + 2n + 1 і, отже,
u n + 1 = u n + 2n + 1. (9)
Збільшуючи n на одиницю, отримаємо:
u n + 2 = u n + 1 + 2n + 3. (10)
Віднімаючи почленно (9) з (10), отримаємо:
u n + 2 - u n + 1 = U n + 1 - U n + 2, або u n + 2 = 2u n + 1 - U n + 2. (11)
Збільшуючи в рівності (11) n на одиницю, будемо мати:
u n + 3 = 2u n + 2 - U n + 1 + 2, (12)
звідки (віднімаючи почленно (11) з (12))
u n + 3 - u n + 2 = 2u n + 2 - 2u n + 1 + u n ,
або u n + 3 = 3u n + 2 - 3u n + 1 + u n.                                                                                            (13)
Отримали одне рівняння третього порядку. Отже, послідовність (8) є поворотна послідовність третього порядку.
Приклад 5. До поворотним відносяться всі періодичні послідовності. Розглянемо послідовність цифр десяткового розкладання числа
= 0,57132132132 ...
Тут u 1 = 5, u 2 = 7, u 3 = 1, u 4 = 3, u 5 = 2, u 6 = 1, u 7 = 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 1 = 0, a 2 = 0, a 3 = 0). Значить послідовність (14) є поворотною послідовністю третього порядку.
Приклад 6. Розглянемо послідовність коефіцієнтів приватного від ділення двох многочленів, розташованих по зростаючим ступенями x. Нехай
P (x) = A 0 + A 1 x +. . . + A l x l
Q (x) = B 0 + B 1 x +. . . + B k x k (B 0 ≠ 0).
Будемо ділити P (x) на Q (x). Якщо P (x) не ділиться на Q (x) без залишку, то розподіл можна продовжувати необмежено. У приватному один за іншим будуть виходити члени:
D 0 + D 1 x + D 2 x 2 + D 3 x 3 +. . . + D n x n +. . .
Розглянемо послідовність
u 1 = D 0, u 2 = D 1,. . . , U n = D n - 1,. . . (16)
і доведемо, що вона є поворотною порядку k (k - ступінь дільника). Фіксуємо довільне натуральне число n, що задовольняє єдиному умові n ≥ l - k + 1, і зупинимося в процесі поділу на члені приватного, що містить x n + k. Тоді в залишку вийде деякий многочлен R (x), що містить x в ступенях вище, ніж n + k. Записуючи співвідношення між діленим, дільником, приватним і залишком, отримаємо наступне тотожність:
A 0 + A 1 x + ... + A l x l = (B 0 + B 1 x +...+ B k x k) • (D 0 + D 1 x + D 2 x 2 + D 3 x 3 + .. . + 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 0 + B 1 x +... + B k x k) • (D 0 + D 1 x + D 2 x 2 + D 3 x 3 +... + D n + k x n + k )
(Залишок R (x) містить x в більш високих ступенях). Тому шуканий коефіцієнт є
D n + k B 0 + D n + k - 1 B 1 +. . . + D n B k . (17)
За попереднім він повинен дорівнювати нулю:
D n + k B 0 + D n + k - 1 B 1 +. . . + D n B k = 0, звідки (B 0 ≠ 0)
D n + k = - D n + k - 1 -. . . - D n (n ≥ l - k + 1). (18)
Це ще одне рівняння порядку k, звідки слід. Що послідовність (16) є поворотна послідовність порядку k.
§ 2. Узагальнення довільних зворотних послідовностей
З усіх розглянутих прикладів найбільш загальний характер має приклад 6. Покажемо, що довільна поворотна послідовність порядку k
u 1, u 2, u 3,. . . , U n,. . . , (19)
задовольняє рівнянню виду
u n + k = a 1 u n + k - 1 + a 2 u n + k - 2 + ... + a k u n (n m 1), (20)
збігається з послідовністю коефіцієнтів приватного, отриманого від ділення многочлена P (x) на многочлен
Q (x) = 1 - a 1 x -. . . - A k x k . (21)
Нехай n - довільне натуральне число, яке задовольняє умові n> k + m - 2; помножимо многочлен Q (x) на u 1 + u 2 x + u 3 x 2 +. . . + U n + 1 x n. Отримаємо:
(1 - a 1 x - a 2 x 2 -... - A k x k) (u 1 + u 2 x +... + u k + M - 1 x k + m - 2 +. . . + U n + 1 x n) = = [u 1 + (u 2 - a 1 u 1) x +. . . + ( u k + M - 1 - a 1 u k + m - 2 -. . . - A k u m - 1) x k + m - 2] +
+ [(U k + m - a 1 u k + m - 1 -... - A k u m) x k + m - 1 +. . . + (U n + 1 - a 1 u n -... - A k u n - k + 1) x n] - - [(a 1 u n + 1 +... + A k u n - k + 2) x n + 1 +. . . + A k u n + 1 x n + k]. (22)
Тут у першій квадратної скобці знаходиться многочлен ступеня не вище l = k + m - 2, коефіцієнти якого не залежать від взятого числа n; позначимо його через P (x):
P (x) = u 1 + (u 2 - a 1 u 1) x +
+. . . + ( u k + M - 1 - a 1 u k + m - 2 -. . . - A k u m - 1) x k + m - 2. (23)
У наступній квадратної скобці знаходиться многочлен, всі коефіцієнти якого дорівнюють нулю, в силу рівності (20). В останній квадратної скобці полягає многочлен, коефіцієнти якого залежать від n, і він не містить членів ступеня нижче n + 1. Позначаючи його через R n (x), перепишемо тотожність (22) у вигляді
P (x) = (1 - a 1 x - a 2 x 2 -... - A k x k ) (U 1 + u 2 x +... + U n + 1 x n) + R n (x). (24)
Звідси видно, що u 1 + u 2 x +. . . + U n + 1 x n представляє приватне, а R n (x) - залишок від ділення P (x) на
Q (x) = 1 - a 1 x - a 2 x 2 -. . . - A k x k, тобто
u 1, u 2,. . . , U n, u n + 1,. . . ,
дійсно є послідовністю коефіцієнтів приватного, одержуваного від ділення многочлена (23) на (21).
У вигляді прикладу розглянемо послідовність Фібоначчі:
u 1 = 1, u 2 = 1, u 3 = 2, u 4 = 3, u 5 = 5, u 6 = 8, u 7 = 13,. . . ,
Так як її члени задовольняють рівняння
u n +2 = u n +1 + u n (n ≥ l),
то тут m = 1, k = 2, a 1 = 1, a 2 = 1 і Q (x) = 1 - x - x 2.
Многочлен P (x) повинен мати ступінь не вище k + m - 2 = 1. За формулою (23) отримуємо:
P (x) = 1 + (1 - 1 • 1) x = 1.
Отже, числа Фібоначчі збігаються з послідовністю коефіцієнтів частки від розподілу 1 на 1 - x - x 2.

§ 3. Вивчення і застосування зворотних послідовностей в курсі середньої школи
Одне з питань, яке доводиться вирішувати в курсі середньої школи щодо арифметичної і геометричної прогресій, а також послідовності квадратів натуральних чисел, полягає в знаходженні суми n членів кожної з цих послідовностей. Нехай
u 1, u 2, u 3,. . . , U n,. . . , (25)
- Поворотна послідовність порядку k, члени якої задовольняють рівнянню:
u n + k == a 1 u n + k - 1 + a 2 u n + k - 2 + ... + a k u n (n m). (26)
Розглянемо нову послідовність, утворену сумами S n чисел (25):
S 1 = u 1, S 2 = u 1 + u 2,. . . , S n = u 1 + u 2 +. . . + U n,. . . , (27)
і покажемо, що ця послідовність сум є також поворотної, порядку k + 1, причому її члени задовольняють рівняння
S n + 1 + k = (1 + a 1) S n + k + (a 2 - a 1) S n + k - 1 +. . . + (A k - a k - 1) S n + 1 - a k S n . (28)
Зауважимо, що
u 1 = S 1, u 2 = S 2 - u 1 = S 2 - S 1,. . . , U n = S n - (u 1 +... + U n - 1) = S n - S n - 1, (29)
Вважаючи S 0 = 0 так, що u 1 = S 1 - S 0, і підставляючи в рівняння (26) замість u 1, u 2, u 3,. . . , U n,. . . , Їх вираження через S 0, S 1, S 2,. . . , S n,. . . , Отримаємо:
S n + k - S n + k - 1 = a 1 (S n + k - 1 - S n + k - 2) + a 2 (S n + k - 2 - S n + k - 3) + .. . + A k (S n - S n - 1),
Звідки S n + k = (1 + a 1) S n + k - 1 + (a 2 - a 1) S n + k - 2 +. . . + (A k - a k - 1) S n - a k S n - 1 (n ≥ m),
або, замінюючи тут n через n +1:
S n + k + 1 = (1 + a 1) S n + k + (a 2 - a 1) S n + k - 1 +. . . + (A k - a k - 1) S n + 1 - a k S n (n ≥ m - 1).
Це - ще одне рівняння порядку k + 1.
Приклади:
a) Геометрична прогресія.
Тут u n = Aq n -1 і
S n = u 1 + u 2 +. . . + U n = a + aq +. . . + Aq n-1.
Так як члени {u n} задовольняють рівнянню виду u n + 1 = qu n , То члени {S n} повинні задовольняти рівнянню
S n (1 + q) S n + 1 - q S n . (30)
b) Послідовність квадратів натуральних чисел.
Тут u n = N 2 і S n = 1 + 2 2 +. . . + N 2.
Так як члени {u n} задовольняють рівнянню
u n + 3 = 3u n + 2 - 3u n + 1 + u n ,
то члени {S n} задовольняють рівнянню виду
S n + 4 = 4S n + 3 - 6u n + 2 + 4S n + 1 - S n.
c) Числа Фібоначчі.
Так як вони задовольняють рівнянню
u n +2 = u n +1 + u n,
то суми їх S n повинні задовольняти рівнянню
S n +3 = 2S n +2 - S n.
§ 4. Формули обчислення будь-якого члена поворотної послідовності. Базис поворотного рівняння
У випадку найпростіших зворотних послідовностей, наприклад арифметичної і геометричної прогресій, послідовності квадратів або кубів натуральних чисел, а також періодичної послідовності, можна знаходити будь-який член послідовності, не вдаючись до обчислення попередніх членів. Але у випадку послідовності числі Фібоначчі або загальної послідовності коефіцієнтів приватного від ділення двох многочленів, на перший погляд це неможливо, і щоб обчислити тринадцяте число Фібоначчі u 13, потрібно знайти попередньо, один за іншим, всі попередні члени (користуючись рівнянням u n +2 = u n +1 + u n):
u 1 = 1, u 2 = 1, u 3 = 2, u 4 = 3, u 5 = 5, u 6 = 8, u 7 = 13, u 8 = 21, u 9 = 34,
u 10 = 55, u 11 = 89, u 12 = 144, u 13 = 233.
У ході детального дослідження структури членів поворотної послідовності можна отримати формули, які дозволяють обчислити в самому загальному випадку будь-який член поворотної послідовності, не вдаючись до обчислення попередніх членів. Ці формули можна розглядати як далекосяжні узагальнення формул для загального члена арифметичної або геометричної прогресій. Нехай
u n + k == A 1 u n + k - 1 + a 2 u n + k - 2 + ... + a k u n                                                                     (31)
- Ще одне рівняння порядку k. Якщо воно виконується для всіх натуральних значень n = 1, 2, 3,. . . , То, поклавши n = 1, отримаємо:
u k + 1 == a 1 u k + a 2 u k - 1 + ... + a k u 1.
Тепер знаючи u 1, u 2, u 3,. . . , U k можна обчислити u k + 1. Вважаючи в рівнянні (31) n = 2 знайдемо:
u k + 2 == a 1 u k + 1 + a 2 u k + ... + A k u 2.
Значить, вже відомо, і значення u k + 2. Якщо m - будь-яке натуральне число, і вже обчислені члени послідовності u 1, u 2, u 3,. . . , u k , u k + 1,. . . , U m + k - 1, то, вважаючи в рівнянні (31) n = m, знайдемо із нього такий член u m + k.
Отже, члени поворотної послідовності порядку k, що задовольняє рівнянню (31), визначаються єдиним чином за допомогою цього рівняння, якщо відомі перші k членів послідовності: u 1, u 2, u 3,. . . , u k .
Вибираючи їх різними способами можна отримати нескінченну безліч різних послідовностей, що задовольняють рівнянню (31). Їх відмінність між собою буде виявлятися вже в перших k членах і буде виявлятися також в подальших членах.
Так, наприклад, рівняння першого порядку
u n + 1 = qu n
задовольняють різноманітні геометричні прогресії зі знаменником q (вони різняться один від одного значеннями першого члена u 1).
Нехай маємо деяку кількість послідовностей, що задовольняють одного й того ж рівняння (31):
x 1, x 2,. . . , X n,. . . ,
y 1, y 2,. . . , Y n,. . . ,
. . . . . . . . . . . . . . . . (32)
z 1, z 2,. . . , Z n,. . . ,
Тоді виконується рівняння:
x n + k == a 1 x n + k - 1 + a 2 x n + k - 2 + ... + a k x n,
y n + k == a 1 y n + k - 1 + a 2 y n + k - 2 + ... + a k y n,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (33)
z n + k == a 1 z n + k - 1 + a 2 z n + k - 2 + ... + a k z n ,
Візьмемо довільні числа A, B,. . . , C, за кількістю послідовностей (32), помножимо всі члени першого з рівнянь на А, другого на В,. . . , Останнього на С і складемо. Тоді вийде рівність:
А x n + k + В y n + k +. . . + З z n + k =
= A 1 (Аx n + k - 1 + Вy n + k - 1 +... + Cz n + k - 1) +
+ A 2 (Аx n + k - 2 + Вy n + k - 2 +... + Cz n + k - 2) + ... + A k (Аx n + Вy n + ... + Cz n). (34)
З нього випливає, що послідовність
t 1 = Аx 1 + Вy 1 +. . . + Cz 1,
t 2 = Аx 2 + Вy 2 +. . . + Cz 2,
. . . . . . . . . . . . . . . . . . . . . (35)
t n = Аx n + Вy n +. . . + Cz n,
. . . . . . . . . . . . . . . . . . . . .
Получающаяся з послідовностей (32) шляхом множення всіх членів першої з них на А, другий на В,. . . , Останньої на С і потім почленного складання послідовностей, задовольняє рівнянню (31). Змінюючи A, B,. . . , C, можна отримати різні значення членів t 1, t 2, t 3, ...
Нехай
u 1, u 2, u 3,. . . , U n,. . . , (36)
- Будь-яка послідовність, яка задовольняє рівнянню (31). Якщо вдасться надати числах A, B,. . . , C такі значення, щоб перші k членів послідовності (35) збіглися б з першими k членами послідовності (36), то співпадуть і всі члени послідовностей (35) і (36), тобто при будь-якому натуральному n будемо мати:
u n = Аx n + Вy n +. . . + Cz n. (37)
Таким чином, відкривається можливість представити будь-яку з нескінченної кількості послідовностей, що задовольняють одному і тому ж поворотному рівнянню порядку k, через деякі з них (32), за формулою (37).
Реалізація цієї можливості залежить від того, чи можливо підібрати числа A, B,. . . , C так, щоб задовольнялися рівняння:
Аx 1 + Вy 1 +. . . + Cz 1 = u 1
Аx 2 + Вy 2 +. . . + Cz 2 = u 2
. . . . . . . . . . . . . . . . . . . . . (38)
Аx k + Вy k +. . . + Cz k = U k
з довільно заданими значеннями правих частин u 1, u 2, u 3,. . . , U k.
Так як невідомими тут є числа A, B,. . . , C, а число рівнянь одно порядку k поворотного рівняння, то звідси випливає, що і кількість невідомих A, B,. . . , C доцільно взяти також рівним k. Відомо, що наявність рішень у системи k алгебраїчних рівнянь (38) з k невідомими A, B,. . . ,
C залежить від того, які коефіцієнти цієї системи: x 1, y 1,. . . , Z 1,. . . , X k, y k,. . . , Z k, тобто від того, які початкові члени послідовностей (32).
Рішення буде існувати при довільних правих частинах u 1, u 2, u 3,. . . , U k, якщо покладемо
x 1 = 0, y 1 = 0,. . . , Z 1 = 0
x 2 = 0, y 2 = 0,. . . , Z 2 = 0
. . . . . . . . . . . . . . . . . . . . (39)
x k = 0, y k = 0,. . . , Z k = 1
У цьому випадку система (38) приймає найпростіший вид, відразу виявляє рішення системи
А = u 1
В = u 2
. . . . . .
C = u k
Можливий інший вибір чисел x 1, y 1,. . . , Z 1,. . . , X k, y k,. . . , Z k, при якому система (38) має рішення, які б не були праві частини рівнянь.
ТЕОРЕМА. Для того щоб система k лінійних алгебраїчних рівнянь (38) з k невідомими мала рішення A, B,. . . , C і притому єдине, за будь-яких значеннях правих частин u 1, u 2, u 3,. . . , U k, необхідно і достатньо, щоб відповідна їй однорідна система
Аx 1 + Вy 1 +. . . + Cz 1 = 0
Аx 2 + Вy 2 +. . . + Cz 2 = 0
. . . . . . . . . . . . . . . . . . . . . (38 ')
Аx k + Вy k +. . . + Cz k = 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)
u n + k == a 1 u n + k - 1 + a 2 u n + k - 2 + ... + a k u n ,
складається з k геометричних прогресій з різними знаменниками. З'ясуємо, за яких умов деяка геометрична прогресія
x 1 = 1, x 2 = q,. . . , X n = q n - 1,. . . , (Q ≠ 0)
задовольняє рівнянню (31). Помічаючи, що
x n + k = q n + k - 1, x n + k - 1 = q n + k - 2,. . . , X n = q n - 1
і підставляючи ці величини в рівняння (31) отримаємо:
q n + k - 1 = a 1 q n + k - 2 + a 2 q n + k - 3 + ... + a n q n - 1,
звідки q k = a 1 q k - 1 + a 2 q k - 2 + ... + a k. (40)
Отже, геометрична прогресія тільки тоді може задовольняти поворотного рівнянню (31) порядку k, коли знаменник прогресії q задовольняє алгебраическому рівнянню (40) ступеня k з тими ж коефіцієнтами, як і в рівнянні (31). Рівняння (40) називається характеристичним для поворотного рівняння (31).
Висновок: поворотного рівнянню порядку k відповідає алгебраїчне рівняння ступеня k з тими ж коефіцієнтами - його характеристичне рівняння. Кожен з коренів характеристичного рівняння являє знаменник геометричної прогресії, що задовольняє даному поворотного рівнянню. У випадку, коли всі корені характеристичного рівняння різні між собою, виходять k різних геометричних прогресій, утворюють базис поворотного рівняння. Отже, в цьому випадку члени будь-якій послідовності, що задовольняє поворотного рівнянню, можна отримати шляхом почленного складання деяких геометричних прогресій (числом k).
При вирішенні деяких зворотних завдань іноді використовують наступну теорему.
ТЕОРЕМА. Нехай a і b - два натуральних числа, причому a <b; тоді число операцій послідовного розподілу в алгоритмі Евкліда, необхідних для відшукання найбільшого загального дільника a і b, не перевершує упятеренного числа цифр числа а, записаного за десятковою системою числення.
§ 6. Зворотні задачі
1. Задача про ханойської вежі
Розглянемо спочатку маленьку витончену головоломку під назвою ханойська вежа, яку придумав французький математик Едуард Люка в 1883 р . Вежа являє собою вісім дисків, нанизаних в порядку зменшення розмірів на один з трьох кілочків. Завдання полягає в тому, щоб перемістити всю вежу на один з інших кілочків, переносячи щоразу лише один диск, і не поміщаючи більший диск на менший.
Будемо вирішувати цю задачу в загальному вигляді, тобто подивимося, що буде у випадку n дисків.
Будемо говорити, що T n є мінімальне число перекладань, необхідних для переміщення n дисків з одного кілочка на інший за правилами Люка.
Розглянемо крайні випадки: Т 0 = 0, T 1 = 1, T 2 = 3, T 3 = 7. Експеримент з трьома дисками дає ключ до загальним правилом переміщення n дисків: спочатку ми переміщаємо (n - 1) менших дисків на будь-який з кілочків (що вимагає Т n - 1 перекладань), потім перекладаємо найбільший диск (одне перекладання) і, нарешті, поміщаємо (n - 1) менших дисків назад на самий великий диск (ще Т n - 1 перекладань). Таким чином, n дисків (при n> 0) можна перемістити найбільше за 2T n - 1 + 1 перекладань (тобто досить перекладань):
T n ≤ 2T n - 1 + 1.
Зараз покажемо, що необхідно 2T n - 1 + 1 перекладань. На деякому етапі ми зобов'язані перемістити найбільший диск. Коли ми це робимо, (n - 1) менших дисків повинні перебувати на одному кілочку, а для того щоб зібрати їх разом, буде потрібно щонайменше Т n - 1 перекладань. Найбільший диск можна перекладати й більше одного разу.
Але після переміщення найбільшого диска в останній раз ми зобов'язані помістити (n - 1) менших дисків (які знову повинні перебувати на одному кілочку) назад на найбільший диск, що також вимагає Т n - 1 перекладань.
Отже,
T n ≥ 2T n - 1 + 1.
Ці два нерівності разом з тривіальним рішенням при n = 0 дають рекурентне співвідношення:
Т 0 = 0
T n = 2T n - 1 + 1 при n> 0 (41)
При досить великому n для обчислення Т n потрібно занадто багато часу, тому отримаємо Т n в простій, компактною, «замкнутої формі», що дозволить обчислити Т n швидко.
Перший спосіб вирішення (вгадування правильного рішення з наступним доказом, що наша здогадка вірна). Обчислимо:
Т 3 = 2 ∙ 3 + 1 = 7; Т 4 = 2 ∙ 7 + 1; Т 5 = 2 ∙ 15 + 1; Т 6 = 2 ∙ 31 + 1 = 63.
Тепер можна зробити припущення, що
Т n = 2 n - 1 при n ≥ 0. (42)
Доведемо методом математичної індукції по числу n:
1) База: n = 0, Т 0 = 2 0 - 1 = 1 - 1 = 0 (вірно);
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n - 1). Доведемо для
t = n: Т n = 2T n - 1 +1 2 (2 n - 1 - 1) + 1 = 2 ∙ 2 n - 1 - 2 + 1 = 2 n - 1
З пунктів 1 і 2 слід: при n ≥ 0 Т n = 2 n - 1
Другий спосіб вирішення.
До обох частин співвідношення (41) додамо 1:
Т 0 +1 = 1,
Т n +1 = 2T n - 1 + 2 при n> 0.
Позначимо U n = T n + 1, тоді отримаємо
U 0 = 1
U n = 2U n - 1 при n> 0.
Рішенням цієї рекурсії є U n = 2 n, отже Т n = 2 n -1.

2. Задача про розрізуванні піци

Формулювання завдання: скільки шматків піци можна отримати, роблячи n прямолінійних розрізів ножем? Або, Яке максимальне число L n областей, на які площину ділиться n прямими?
SHAPE \ * MERGEFORMAT
2
L 1 = 2
2
1
3
4
L 2 = 4
1
L 0 = 1

1
Знову почнемо з розгляду крайніх випадків.
Експеримент з трьома прямими показує, що додана третя пряма може розсікати найбільше три старих області незалежно від того, як розташовані перші дві прямі:


1b
2
4a
4b
3a
3b
Таким чином, L 3 = 4 + 3 = 7 - найбільше, що можна зробити.
Узагальнюючи, приходимо до наступного висновку: нова n-я пряма (при n> 0) збільшує число областей на k ó коли розсікає k старих областей ó коли перетинає колишні прямі в (k - 1) різних місцях. Дві прямі можуть перетинатися не більше ніж в одній точці. Тому нова пряма може перетинати (n - 1) старих прямих не більше ніж в (n - 1) різних точках, і ми повинні мати k ≤ n. Встановлена ​​верхня межа:
L n ≤ L n - 1 + n при n> 0
У цій формулі можна досягти рівності наступним чином: проводимо n-у пряму так, щоб вона не була паралельна ніякої іншої прямої (отже, вона перетинає кожну з них) і так, щоб вона не проходила через жодну з наявних точок перетину (отже, вона перетинає кожну з прямих у різних місцях). Тому рекурентне співвідношення має вигляд:

L 0 = 1
L n = L n - 1 + n при n> 0
Тепер отримаємо рішення в замкненій формі.
L n = L n - 1 + n = L n - 2 + (n-1) + n = L n - 3 + (n-2) + (n-1) + n = ... = L 0 + 1 + 2 + + ... + (n-2) + (n-1) + n = 1 +
L n = + 1 при n ≥ 0 (43)
Доведемо отримане рівність методом математичної індукції.
1) База: n = 0, L 0 = = 1 (вірно);
2) Індуктивний перехід: нехай доведено для всіх чисел t ≤ (n-1). Доведемо для t = n:
L n = L n -1 + n = =
З пунктів 1 і 2 слід: при n ≥ 0
L n = + 1
3
А тепер невелика варіація на тему прямих на площині: припустимо, що замість прямих ліній ми використовуємо ламані лінії, кожна з яких представлена ​​одним «зігом». Яке максимальне число Z n областей, на які площину ділиться n такими ламаними лініями?
Окремі випадки:
2
1
1
4
6
5
7
2
Z 1 = 2
Z 2 = 7



Ламана лінія подібна двом прямим з тією лише відмінністю, що області зливаються, якщо «дві» прямі не продовжувати після їх перетину:
1
4
3
2
Області 2, 3 і 4, які були б розділені за наявності двох прямих, перетворюються в єдину область у випадку однієї ламаної лінії, тобто ми втрачаємо дві області. І якщо привести все в належний порядок, то точка зламу повинна лежати «по той бік» перетинів з іншими лініями, і ми втрачаємо тільки дві області на одну лінію. Таким чином,
Z n = L 2 n - 2n = = 2n 2-n +1 при n ≥ 0 (44)
Порівнюючи рішення в замкненій формі (43) і (44), ми приходимо до висновку, що при великому n,
L n ~ ,
Z n ~ 2n 2,
так що ламані лінії дають приблизно в чотири рази більше областей, ніж прямі.

Глава 2 (практична частина)
1. Розглянемо послідовність квадратів натуральних чисел:
u 1 = 1 2, u 2 = 2 2, u 3 = 3 2,. . . , U n = N 2,. . . (*)
Тут u n + 1 = (n + 1) 2 = n 2 + 2n + 1 і, отже,
u n + 1 = u n + 2n + 1. (1)
Збільшуючи n на одиницю, отримаємо:
u n + 2 = (n + 2) 2 = n 2 + 4n + 4 = (n 2 + 2n + 1) + 2n + 3 = u n + 1 + 2n + 3.
u n + 2 = u n + 1 + 2n + 3. (2)
Віднімаючи почленно (1) з (2), отримаємо:
u n + 2 - u n + 1 = (U n + 1 + 2n + 3) - (u n + 1 = u n + 2n + 1) = u n + 1 - U n + 2,
u n + 2 = 2u n + 1 - U n + 2. (3)
Збільшуючи в рівності (3) n на одиницю, будемо мати:
u n + 3 = (n + 3) 2 = n 2 + 6n + 9 = (n 2 + 4n + 4) + 2n + 5 = u n + 2 + 2n + 5,
u n + 3 = u n + 2 + 2n + 5. (4)
Віднімаючи почленно (2) з (4), отримаємо:
u n + 3 - u n + 2 = (u n + 2 + 2n + 5) - (u n + 1 + 2n + 3) = u n + 2 - U n + 1 + 2,
u n + 3 = 2u n + 2 - U n + 1 + 2, (5)
Віднімаючи почленно (3) з (5), отримаємо:
u n + 3 - u n + 2 = (2u n + 2 - U n + 1 + 2) - (2u n + 1 - U n + 2) = 2u n + 2 - 3u n + 1 + u n,
або u n + 3 = 3u n + 2 - 3u n + 1 + u n.. (6)
Отримали одне рівняння третього порядку, тобто k = 3, a 1 = 3, a 2 = -3, a 3 = 1.
Отже, послідовність (*) є поворотна послідовність третього порядку.
2. Розглянемо послідовність кубів натуральних чисел:
u 1 = 1 3, u 2 = 2 3, u 3 = 3 3,. . . , U n = N 3,. . . (**)
Тут u n + 1 = (n + 1) 3 = n 3 + 3n 2 + 3n + 1 і, отже,
u n + 1 = u n + 3n 2 + 3n + 1. (7)
Збільшуючи n на одиницю, отримаємо:
u n + 2 = (n + 2) 3 = n 3 + 6n 2 + 12n + 8 = (n 3 + 3n 2 + 3n + 1) + 3n 2 + 9n + 7 = = u n + 1 + 3n 2 + 9n + 7,
u n + 2 = u n + 1 + 3n 2 + 9n + 7. (8)
Віднімаючи почленно (7) з (8), отримаємо:
u n + 2 - u n + 1 = (U n + 1 + 3n 2 + 9n + 7) - (u n + 3n 2 + 3n + 1) = u n + 1 - U n + 6n + 6,
u n + 2 = 2u n + 1 - U n + 6n + 6. (9)
Збільшуючи в рівності (9) n на одиницю, будемо мати:
u n + 3 = (n + 3) 3 = n 3 + 9n 2 + 27n + 27 = (n 3 + 6n 2 + 12n + 8) + 3n 2 + 15n + 19 = u n + 2 + 3n 2 + 15n + 19,
u n + 3 = u n + 2 + 3n 2 + 15n + 19. (10)
Віднімаючи почленно (8) з (10), отримаємо:
u n + 3 - u n + 2 = (u n + 2 + 3n 2 + 15n + 19) - (u n + 1 + 3n 2 + 9n + 7) = u n + 2 - U n + 1 + 6n + 12,
u n + 3 = 2u n + 2 - U n + 1 + 6n + 12. (11)
Віднімаючи почленно (9) з (11), отримаємо:
u n + 3 - u n + 2 = (2u n + 2 - U n + 1 + 6n + 12) - (2u n + 1 - U n + 6n + 6) = 2u n + 2 - 3u n + 1 + u n + 6 ,
або u n + 3 = 3u n + 2 - 3u n + 1 + u n + 6 (12).
Збільшуючи в рівності (12) n на одиницю, будемо мати:
u n + 4 = (n + 4) 3 = n 3 + 12n 2 + 48n + 64 = (n 3 + 9n 2 + 27n + 27) + 3n 2 + 21n + + 37 = u n + 3 + 3n 2 + 21n + 37,
u n + 4 = u n + 3 + 3n 2 + 21n + 37. (13)
Віднімаючи почленно (10) з (13), отримаємо:
u n + 4 - u n + 3 = (u n + 3 + 3n 2 + 21n + 37) - (u n + 2 + 3n 2 + 15n + 19) = = u n + 3 - U n + 2 + 6n + 18,
u n + 4 = 2u n + 3 - U n + 2 + 6n + 18. (14)
Віднімаючи почленно (11) з (14), отримаємо:
u n + 4 - u n + 3 = (2u n + 3 - U n + 2 + 6n + 18) - (2u n + 2 - U n + 1 + 6n + 12) = = 2u n + 3 - 3u n + 2 + u n + 1 + 6 ,
або u n + 4 = 3u n + 3 - 3u n + 2 + u n + 1 + 6. (15)
Віднімаючи почленно (12) з (15), отримаємо:
u n + 4 - u n + 3 = (3u n + 3 - 3u n + 2 + u n + 1 + 6) - (3u n + 2 - 3u n + 1 + u n + 6) = 3u n + 3 - 6u n + 2 + 4u n + 1 - u n,
або u n + 4 = 4u n + 3 - 6u n + 2 + 4u n + 1 - u n. (15)
Отримали одне рівняння четвертого порядку, тобто k = 4, a 1 = 4, a 2 = -6, a 3 = 4, a 4 = - 1.
Отже, послідовність (**) є поворотна послідовність четвертого порядку.
3. Перевіримо, що умова теореми:
Для того щоб система k лінійних алгебраїчних рівнянь
Аx 1 + Вy 1 +. . . + Cz 1 = u 1
Аx 2 + Вy 2 +. . . + Cz 2 = u 2
. . . . . . . . . . . . . . . . . . . . . (16)
Аx k + Вy k +. . . + Cz k = U k
з k невідомими мала рішення A, B,. . . , C і притому єдине, за будь-яких значеннях правих частин u 1, u 2, u 3,. . . , U k, необхідно і достатньо, щоб відповідна їй однорідна система
Аx 1 + Вy 1 +. . . + Cz 1 = 0
Аx 2 + Вy 2 +. . . + Cz 2 = 0
. . . . . . . . . . . . . . . . . . . . . (17)
Аx k + Вy k +. . . + Cz k = 0
мала б одне тільки нульовий розв'язок: A = B =. . . = C = 0 - виконується в окремих випадках
x 1 = 0, y 1 = 0,. . . , Z 1 = 0
x 2 = 0, y 2 = 0,. . . , Z 2 = 0 (18)
x k = 0, y k = 0,. . . , Z k = 1
x 1 = 1, y 1 = 1,. . . , Z 1 = 1
x 2 = 0, y 2 = 1,. . . , Z 2 = 1 (19)
x k = 0, y k = 0,. . . , Z k = 1
1) x 1 = 0, y 1 = 0,. . . , Z 1 = 0
x 2 = 0, y 2 = 0,. . . , Z 2 = 0
x k = 0, y k = 0,. . . , Z k = 1
Тоді однорідна для (16) система (17) набуде вигляду


А • 1 = 0
У • 1 = 0
. . . . . .
C • 1 = 0
А = 0
У = 0
. . . . . .
C = 0
Т. е. A = B =. . . = C = 0.
Отримали, що k лінійних алгебраїчних рівнянь (16) з k невідомими має єдине рішення
A = B =. . . = C = 0.
2) x 1 = 1, y 1 = 1,. . . , Z 1 = 1
x 2 = 0, y 2 = 1,. . . , Z 2 = 1
x k = 0, y k = 0,. . . , Z k = 1
Тоді однорідна для (16) система (17) набуде вигляду
А • 1 + В • 1 +. . . + C • 1 = 0
В • 1 +. . . + C • 1 = 0
. . . . . . . . . . . . . . . . . . . . .
C • 1 = 0
Вирішуючи цю систему з кінця, отримаємо A = B =. . . = C = 0. Отримали, що k лінійних алгебраїчних рівнянь (16) з k невідомими має єдине рішення A = B =. . . = C = 0.

Висновок
У даній роботі поставлені цілі досягнуто.
У роботі вивчено основні теоретичні відомості про зворотних послідовностях, наведені приклади таких послідовностей, також доведені деякі теореми. Потрібно зауважити, що частина теоретичного матеріалу розглядається саме через приклади, за допомогою яких виводяться основні формули теорії зворотних послідовностей. Також порушено тему «поворотні завдання», в роботі детально розібрані деякі з них. Третя глава присвячена вивченню та застосуванню зворотних послідовностей в шкільному курсі математики, що можна включити в навчальну програму факультативу з математики в середній школі.
У практичній частині застосовані отримані знання теорії зворотних послідовностей. А саме: доведено за визначенням, що послідовності є зворотніми та перевірено умова виконання теореми в окремих випадках.
Тема «Поворотні послідовності» не є ізольованою, Вона близька до шкільного курсу математики (арифметична і геометрична прогресії, послідовності квадратів і кубів натуральних чисел і т.д.), використовується у вищій алгебрі, геометрії, математичному аналізі та інших математичних дисциплінах. Теорія зворотних послідовностей складає особливу главу математичної дисципліни, званої обчисленням кінцевих різниць; є приватну главу про послідовностях.
Таким чином, в даній курсовій роботі вивчена дуже важлива і актуальна на сьогоднішній день тема.

Список літератури
1. Грехем, Р. Конкретна математика. Підстава інформатики. / Р. Грехем, Д. Кнут, О. Паташнік. Пер. з англ. - М.: Світ, 1998. - С. 17-37.
2. Маркушевич А. І. Зворотні послідовності. Популярні лекції з математики. - М.: Наука, 1950.
3. Мантуров О. В. Математика в поняттях, визначеннях і термінах. Ч.2 / О. В. Мантуров, Ю. К. Солнцев, Ю. І. Соркін, Н. Г. Федін; Під. ред. Л. В. Сабініна. - М.: Просвещение, 1982. - С. 207-208.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
87.7кб. | скачати


Схожі роботи:
Зворотні задачі
Зворотні зв`язки в живих системах
Інтерфейси зворотні виклики внутрішні класи
Зворотні матриці над кільцем цілих чисел
Послідовності
Багатовимірні послідовності Фібоначчі
Математичні послідовності Межа функції
Програмування рекурентні послідовності та співвідношення
Межа послідовності Теорема Штольца
© Усі права захищені
написати до нас