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

План

1. Поняття зворотної послідовності.

2. Приклади зворотних послідовностей.

3. Зв’язок зворотного рівняння із сумами членів послідовності.

4. Загальна формула для знаходження будь-якого члену зворотної послідовності.

5. Приклади, та розв’язки задач із використанням теорії зворотної послідовності.

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

Будемо записувати послідовності у вигляді

або коротко {un}. Якщо існує натуральне число k і числа a1,a2, ,ak (дійсні або уявні, причому ak¹0 ) такі, що, починаючи з деякого номера m і для всіх наступних номерів

то послідовність (1) називається зворотною послідовністю порядку k, а співвідношення (2) — зворотнім рівняння порядку k. Таким чином, зворотна послідовність характеризується тим, що кожний член її (починаючи деякого з них) виражається; через одне і ту саму кількість k безпосередньо передуючих йому членів по формулі (2).

Приклади зворотних послідовностей.

Приклад I. Геометрична прогресія.

Нехай маємо геометричну прогресію

для неї рівняння (2) набуває вигляду

Тут k=1 і a1=q. Таким чином геометрична прогресія є зворотною послідовністю першого порядку.

Приклад 2. Арифметична прогресія.

У випадку арифметичної прогресії

маємо

співвідношення, що не має вигляду рівняння (2) .Однак, якщо ми розглянемо два співвідношення, написані для двох сусідніх значень n:

то одержимо з них шляхом почленного віднімання

рівняння вигляду (2). Тут k=2, a1=2, a2=-1. Отже арифметична прогресія є зворотною послідовності порядку 2.

Приклад 3. Числа Фібоначчі. Задовольняють зворотному рівнянню другого порядку

Приклад 4 Послідовність квадратів натуральних чисел

Тут un+1=(n+1)2=n2+2n+1 і відповідно

Збільшуючи n на одиницю, отримаємо

І, отже (віднімаючи почленно (4) від (5))

Або

Збільшуючи в рівнянні (6) n на одиницю, будемо мати

Звідки (почленно віднімаючи (6) від (7))

або

Ми отримали зворотне рівняння третього порядку. Отже, послідовність (8) є зворотною послідовністю третього порядку. Подібним чином можна переконатися, що послідовність кубів натуральних чисел є зворотною послідовністю четвертого порядку, члени якої задовольняють рівняння

Приклад. 5. До зворотних послідовностей відносяться всі періодичні послідовності.: Розглянемо, наприклад, послідовність цифр десяткового розкладу числа

Тут

Очевидно, що

Щоб подати це рівняння у вигляді (2), перепишемо його наступним чином:

Звідси видно, що це зворотне рівняння третього порядку (k=3, a1=0, a2=0, a3=1). Отже, послідовність (8) є зворотною послідовність третього порядку.

Приклад 6. Розглянемо тепер послідовність коефіцієнтів частки від ділення двох многочленів розташованих по зростаючих степенях x. Нехай

P(x)=A0+A1x+…+Alxl

Q(x)=B0+B1x+…+BKxK (B0¹0)

Будемо ділити Р(х) на Q(x); якщо Р(x) не ділиться на Q(x) без залишку, то ділення можна продовжувати нескінченно. У частці один за іншим будуть одержуватись члени

Розглянемо послідовність

і доведемо, що вона є зворотною послідовністю порядку k. Для цього зафіксуємо довільне натуральне число n, яке задовольняє рівняння n³k+1 — зупинимося в процесі поділу на члені частки, що має xn+k. Тоді в залишку вийде деякий многочлен R(х), що містить х у ступенях вище ніж n+k. Записуючи співвідношення між діленим і дільником, часткою й залишком отримаємо наступну тотожність:

Знайдемо коефіцієнти при xn+k у лівій та правій частині цього рівняння і прирівняємо їх між собою. Так як n+k³l+1, то коефіцієнти при xn+k у лівій частині рівні нулю. Тому повинен дорівнювати нулю і коефіцієнт при xn+k у правій частині. Проте члени з xn+k входять тільки в добуток (B0+…+Bkxk)(D0+…+Dn+kxn+k). Тому шуканий коефіцієнт є

Звідси

Це — зворотне рівняння порядку k, звідки і випливає, що послідовність (9) зворотна послідовність порядку k.

Одне з питань, що стосується арифметичної й геометричної прогресій, а також послідовностей квадратів натуральних чисел – це відшукування суми n членів кожної з цих послідовностей.

Нехай

Зворотна послідовність порядку k, члени якої задовольняють рівняння

Розглянемо нову послідовність, утворена сумами sn чисел (10)

і покажемо, що ця послідовність сум є також зворотною послідовністю, порядку k+1, причому її члени задовольняють рівняння

Для доведення слід відмітити, що

Покладаючи, що s0=0, так, що u1=s1-s0, підставляючи в рівняння (11) замість u1,u2,u3,…un,…, їх значення через s0, s1, .,sn…,отримаємо

звідки

або, замінюючи тут n на n+1:

Це зворотнеє рівняння порядку k+1.

Для прикладу

1. Геометрична прогресія. В даному випадку un=aqn-1 і sn=u1+u2+…+un=a+aq+…+aqn-1. Оскільки члени {un} задовольнять рівняння виду un+1=qun, то члени {un}повинні задовольняти рівняння

2. Послідовність квадратів натуральних чисел. Маємо un=an і sn=12+22+…n2. Оскільки члени {un} задовольняють рівняння

то члени {sn} задовольняють рівняння

3. Числа Фібоначчі. Так як вони задовольняють рівняння

то відповідно їхні суми повинні задовольняти рівняння

У випадку найпростіших зворотних послідовностей, наприклад арифметичної й геометричної прогресій, послідовностей квадратів або кубів натуральних чисел, а також періодичної послідовності, ми можемо знаходити будь-який член послідовності, не звертаючись до обчислення попередніх членів. У випадку ж послідовності чисел Фібоначчі доволі складно обчислити довільний її член.

Можна вивести формули, які дозволять знайти будь-який член, не обраховуючи попередніх. Розглянемо структуру зворотної послідовності. Отже, нехай

Як відомо, це зворотне рівняння порядку k. Якщо воно виконується для всіх натуральних n, то поклавши n=1, отримаємо

Отже, знаючи u1,u2, .,uk, можна обчислити uk+1. Покладаючи в рівнянні (12) n=2, знайдемо

Тепер вже відомо значення uk+2. Узагалі, якщо m-будь-яке натуральне число, і ми обчислили члени послідовності

то, покладаючи в рівнянні (12) n=m, зайдемо з нього наступний член um+k.

Отже, члени зворотної послідовності порядку k, які задовольняють рівняння (12), задаються однозначно, якщо відомі перші k членів послідовності u1,u2, .uk. Вибираючи їх різними способами, можемо отримати нескінченну кількість різних послідовностей, які задовольняють початкове рівняння.

Нехай ми маємо деяку кількість таких послідовностей, які задовольняють рівняння (12)

Тоді повинні виконуватися рівняння

Взявши довільні числа A,B,…,C, по кількості послідовностей (13), помноживши всі члени першого рівняння (14) на A, другого на B,…, останнього на С і, додавши, отримаємо рівняння

З нього випливає, що послідовність

задовольняє дане рівняння (12). Користуючись довільністю у вибору чисел А,B, .,С, ми можемо, змінюючи ці числа, одержувати, узагалі говорячи, різні значення членів, t1,t2, .

Нехай тепер

яка-небудь послідовність, що задовольняє рівнянню (12); покажемо, що можна підібрати числа A,B,…,C такі, щоб значення перших k членів послідовності (14`) співпадали з першими k членами послідовності членів послідовності (15). З цього буде слідувати, що при будь-якому n буде виконуватися рівність

Таким чином, перед нами відкривається можливість подавати кожну з нескінченної безлічі послідовностей, що задовольняють тому самому зворотному рівнянню порядку k через деякі з них (13) по формулі (16). Реалізація цієї можливості залежить від того, чи можна підібрати числа A,B,…,C так, щоб задовольнялися рівняння:

з довільно заданими значеннями лівих частин u1,u2, .uk.

Щоб дана система (17) мала розв’язок, необхідно та достатньо щоб визначник

не дорівнював нулю.

Система k послідовностей (13), через які члени довільної послідовності, які задовольняють дане рівняння (12), і виражаються за формулами (16) називаються базисом зворотного рівняння.

Для кожного зворотного рівняння порядку k існує нескінченна кількість різних послідовностей, яке його задовольняють. Кожну з них можна скласти з k послідовностей, які задовольняє це рівняння і утворюють його базис, шляхом множення кожної з k послідовностей на A,B,…,C і по членного сумування.

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

Приклад. Нехай дано зворотне рівняння другого порядку

Його базис повинен складатися з двох послідовностей

Ми виберемо їх, поклавши

(кількість xn і yn як сказано визначається порядком зворотного рівняння). Оскільки зворотне рівняння, переписане у вигляді

показує, що різниця сусідніх членів послідовності є постійною, тобто дана послідовність є арифметичною прогресією. У випадку послідовності {xn} із початковим членами x1=1 і x2=1 ми отримаємо арифметичну прогресію з різницею в нуль.

а у випадку послідовності {yn} із початковими членами y1=0 і y2=1 – арифметичну прогресію різницею 1.

За формулою (16) член. будь-якої зворотної послідовності, що задовольняє даному рівнянню, може бути поданий у виді.

де А і В повинні бути визначені з рівнянь

Звідси слідує що

Маємо

і, отже,

Це формула для обчислення будь-якого члена послідовності, яка задовольняє зворотне рівняння

Покладаючи u1=a, u2-u1=d, можна подати її у вигляді

Це і є відома формула для загального члена арифметичної прогресії.

Покажемо, що при деяких загальних умовах можна знайти базис зворотного рівняння.

який складається з k геометричних прогресій з різними знаменниками. Спочатку з'ясуємо, при яких умовах деяка геометрична прогресія

буде задовольняти рівняння (12). При цьому враховуючи, що

і підставляючи дані значення замість un, отримаємо

звідки

Отже геометрична прогресія тільки тоді може задовольняти зворотне рівняння (12) порядку k, коли знаменник прогресії q задовольняє алгебраїчне рівняння (18) степеня k із тими самими коефіцієнтами, що і рівняння (12).

Рівняння (18) називається характеристичним для зворотного рівняння (12). Якщо q=α – який-небудь корінь характеристичного рівняння (дійсний чи уявний), то поклавши

отримаємо геометричну прогресію з першим членом x1=1 і знаменником α, яка задовольняє рівняння (12). Справді, за умовою, α є корінь рівняння (18), тобто

Домножаючи обидві частини на αn-1, де nεN, отримаємо

Тобто послідовність (19) задовольняє рівняння (12).

Отже, кожному кореневі q=α характеристичного рівняння (18) відповідає геометрична прогресія (19) зі знаменником α, що задовольняє зворотному рівнянню (12).

Щоб скласти базис з одних лише геометричних прогресій з різними знаменниками, потрібно мати їх у достатній кількості, рівній k, а для цього потрібно мати k різних коренів характеристичного рівняння.

Нехай, всі корені характеристичного рівняння різні

Тоді отримаємо k геометричних прогресій, які задовольняють рівняння (12).

Оскільки дана система послідовностей (20) складає базис рівняння (12), можна підібрати такі числа A,B,…,C, що при довільному n.

Як приклад застосування даних результатів розглянемо послідовність чисел Фібоначчі. Для них зворотне рівняння має вигляд

Відповідно до рівняння (18) характеристичне рівняння має вигляд

Коренем цього рівняння є два різних дійсних корені

Туму загальний член послідовності Фібоначчі можна записати так

Для того, щоб знайти невідомі коефіцієнти A і B, покладемо n=1 і n=2; отримаємо

Коренями даної системи є числа

і, відповідно,

або

Це і формула для знаходження чисел Фібоначчі.

Розглянемо ще один приклад у якому корінь характеристичного рівняння є кратним. Такою послідовністю може бути послідовність квадратів натуральних чисел. Для них зворотне рівняння має вигляд.

і, отже, характеристичне рівняння таке:

або

Воно володіє тільки одним чотирьохкратним коренем: q=1; тому ми й одержуємо тут тільки одну геометричну прогресію зі знаменником 1, члени якої, задовольняють даному зворотному рівнянню.

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

Тепер нехай маємо зворотне рівняння

де — біноміальні коефіцієнти порядку k, що відповідає характеристичному рівнянню

яке може бути подане у вигляді.

Воно має k – кратний корінь q=α; очевидно, що

Розглянемо взагалі наступні тотожності;

Де m=0,1,2,…,k-1, або

Рівність, що відповідає m=0, має вигляд

При цьому можна помітити

Або

Домножимо кожне рівняння (22) (m=1,2, .,k-1) на відповідний множник k(k-1)…(k-m+1) і після цього скористаємося (24), перепишемо його у вигляді

Доведемо тепер, що при m=0,1,2,…,k-1 виконуються слідуючи рівності:

Справді, рівність, яка відповідає m=0, співпадає з (23) і, отже, справедлива.

Міркуючи по індукції, припустимо, що рівності (26) уже доведені для m=0,1,…j (jk-2), і доведемо що рівність, яка відповідає m=j+1 також справедлива. З цією метою введемо многочлен степеня j+1:

Домножаючи рівняння (61) при m=1,2,…j відповідно на числа β1, β2, .,βj, отримаємо

Запишемо рівняння (25), яке відповідає значенню m=j+1, у вигляді

(ми тут використали те, що (k-j)…k=f(k), (k-j-1)… (k-1)=f(k-1),…,(k-μ-j)…(k-j)=f(k-j), .).

Додаючи (28) і (29) почленно, будемо мати

Проте в наслідок (27)

Тому отриманий результат набуває вигляду

Це і є рівність (26) для m=j+1. Таким чином доведена рівність (26).

Розглянемо, нарешті, довільний многочлен степеня не вище k-1:

Домножаючи рівність (26) при m=1,2,…,k-1 відповідно на A0, A1,…, Ak-1, отримаємо

Додаючи їх почленно, будемо мати

або

Отже, довільний многочлен P(x) степеня не вище k-1 задовольняє співвідношенню (30).

Покладемо, зокрема, Р(х)=(х+n-1)m, де n ‑ довільне натуральне число і m — ціле, 0<m≤k-1. Тоді рівність (30) набуде вигляду

Або, домножаючи на αk+n-1 і замінюючи на 1:

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

Якщо ми встановимо, що вони утворюють базис, то звідси. буде .випливати, що загальний член довільної послідовності, що задовольняє рівняння (21), має вигляд

де Q(x)=B0+B1x+…+Bk-1xk-1 – многочлен степеня не вище k-1 з довільними коефіцієнтами.

Достатньо показати, що система k лінійних рівнянь

має розв’язок відносно невідомих при будь-яких u1,…uk тобто в силу положень, що були запропоновані вище, система

має тільки нульовий розв’язок. Проте рівняння останньої системи означають, що

тобто, що рівняння

степеня не вище k-1 має, в крайньому випадку, k різних корені: 0,1,2,…,k-1. Звідси випливає що

Отже послідовності (32) утворюють базис зворотних послідовностей, які задовольняють рівнянню (21).

У випадку довільної зворотної послідовності, яка задовольняє загальне рівняння

характеристичне рівняння

може мати деякий корінь α кратності a, корінь β кратності b,…, корінь γ кратності c, а всього a+b+…+c=k коренів.

Для цього найбільш загального випадку можна показати, що базис складається з наступних k послідовностей

Тому

Де Q(x), R(x), ., S(x) – деякі фіксовані многочлени, степеня не вище a-1, b-1,…,c-1 відповідно.

Отже, загальний член un будь-якої зворотної послідовності має вигляд суми добутків многочленів відносно n-1 (або, що зводиться до того ж, відносно n) на загальні члени геометричних прогресій, знаменники яких дорівнюють кореням характеристичного рівняння (35).

У випадку, коли всі корені останнього рівняння— прості, зазначені многочлени є сталими і загальний член зворотної послідовності подається у виді суми членів геометричних прогресій.

Можна довести також справедливість оберненого твердження. А саме, будь-яка послідовність {un}, загальний член якої виражається за формулою, (36), є зворотною. Відповідне характеристичне рівняння (35) будується за його коренях α,β, .,γ і за їх крайностях a,b,…,c (які являють собою степені многочленів Q,R, ,S, збільшені на одиницю). Звідси негайно знаходиться зворотне рівняння (34).

Розглянемо у виді прикладу послідовність.

Порівнюючи з (36), доходимо висновку, що корені характеристичного рівняння такі: α=2, β=3, причому кратність α дорівнює 2+1=3. Тому характеристичне рівняння повинно мати вигляд

а зворотне рівняння запишеться так;

Покажемо отримані результати на конкретних прикладах. Як відомо члени арифметичної прогресії задовольняють рівняння

квадрати натуральних чисел — рівняння

а куби — рівняння

Очевидно, що всі ці рівняння є частинними випадками рівняння

(тут α=1). Загальний член будь-якої послідовності, що задовольняє цьому рівнянню повинний мати вигляд [формула (33)]

Щоб знайти коефіцієнти B0, B1,…Bk-1 достатньо розв’язати наступну систему k лінійних алгебраїчних рівнянь із k невідомими:

У випадку арифметичної прогресії k=2 формула (33) набуде вигляду

А система (39) вигляду

Очевидно, що B0=u1 є перший член прогресії, а B1=u 2- u1=d – різниця прогресії. Отже,

Ми отримали відому формулу.

Немає потреби робити відповідні викладення для випадку послідовності квадратів або кубів натуральних чисел, тому що ми із самого початку знаємо тут, що un=n2 і un=n3. Однак має деякий інтерес застосувати співвідношення .(38) і (39) до виведення формул для суми членів арифметичної прогресії, а також суми, квадратів або кубів натуральних чисел.

Раніше було доведено, що якщо члени деякої послідовності {un} задовольняють рівняння виду

то суми {sn} членів цієї послідовності задовольняють рівняння

У випадку рівняння (37), очевидно, що

Тому

І рівняння для {sn} може бути подане у вигляді

або

Таким чином, якщо ;послідовність {un} задовольняє рівняння виду (37) порядку k, то послідовність відповідних сум {sn} задовольняє рівняння такого ж виду, але порядку k+1. У випадку арифметичної прогресії k=2, а для послідовності квадратів натуральних чисел k=3 і для послідовності кубів k=4; отже, для послідовностей відповідних сум потрібно в указаних вище рівностях (37), (38), (39) брати k на одинці більшим: 3,4 і 5.

а) Сума членів арифметичної прогресії. На основі зроблених зауважень, sn виражаються із формули (38) із заміною (un на sn) при k=3. Отже

Коефіцієнти B0, B1, B2 визначаються з системи (39) ( із тією ж заміною un на sn при k=3)

Розв’язуючи її, отримаємо

Отже

Теорія зворотних послідовностей часто використовують при розв’язуванні задач, що стесуються саме послідовностей. Як приклад розглянемо деякі.

Задача 1. Довести, що кожний член послідовності

є цілим числом. Знайти всі значення nZ, при, кожному з яких число an ділиться на 3.

Розв’язок. Оскільки , то a-n=an, а тому достатньо розв’язати задачу для випадку nZ+. Оскільки кожен член послідовності є сумою відповідних членів двох геометричних прогресій із знаменниками та , то характеристичне рівняння послідовності матиме вигляд:

або

а члени послідовності задовольняють зворотнє рівняння вигляду

з початковими умовами a0=0, a1=1, a2=4.

З такого завдання послідовності випливає, що всі її члени – цілі числа, а залишки від ділення членів послідовності на 3 мають утворювати деяку послідовність.

Знайдемо перші члени послідовності цих залишків. Маємо таку послідовність: d0=0, d1=1, d2=1, d3=0, d4=2, d5=2, d6=0, d7=1, d8=1, d9=0, ., яка є періодичною з періодом T=6, а діляться на 3 тільки ті члени вигляду a3k, kZ.

Задача 2. Довести, що кожен член послідовності

Є натуральним числом і переставляється у вигляді 5m2 або m2 (m0N) при парному чи непарному n відповідно.

Розв’язок. Розглянемо допоміжну послідовність . Легко помітити що

Характеристичне рівняння цієї послідовності

Або

Відповідно зворотне рівняння буде таким

З початковими умовами b1=1, b2=. Тепер доведемо методом математичної індукції по kN, що b2k-1 є цілим, а b2k є числом вигляду m, mN (це рівносильне твердженню задачі)

При k=1 твердження вірне: b1=1, b2=

Нехай тепер при деякому kN b2k-1 – ціле, а b2k=m. Тоді

Тобто теж є цілим, та

Тобто має вигляд m1, де m1=4m-b2k-1 є натуральним числом.

Література

1. Маркушевич А. І. Зворотні послідовності.‑М.: Наука, 1975

2. Б. А. Захаров О. А. Сарана Зворотні послідовності //У світі математики – т.6, вип. 4 С. 56-54.