Державна установа освіти
Гімназія № 8 г . Вітебська
БАГАТОВИМІРНИХ
послідовності Фібоначчі
Вітебськ, 2009

Зміст
Введення, основні поняття
1. Властивості послідовності
2. Упорядкування, обчислення елементів послідовності
3. Деякі залежності між уявними трійками
4. Практичне застосування, доповнення
4.1 Рішення завдання «Математики грають»
4.2 Фігури в декартових системах координат
Заключна частина
Напрямки для досліджень

Література

Введення, основні поняття

Широко відома класична послідовність чисел Фібоначчі, в якій перші два елементи дорівнюють одиниці (F ₁ = F ₂ = 1), а кожний наступний дорівнює сумі двох попередніх. (F _{i +2} = F _{i +1} + F _i.) У даній роботі представлена послідовність, схожа з побудови з послідовністю Фібоначчі, але складається не з чисел, а з трійок чисел (Далі будемо називати її тривимірною послідовністю Фібоначчі). Мета даної роботи - знайти формули залежності між її членами, рекурентні співвідношення, загальні формули. Також в роботі розглянуті можливі застосування даної послідовності: при вирішенні завдання з турніру юних математиків (м. Мінськ, 2007 р .), І крім цього, були розглянуті фігури в декартових системах координат, чиї вершини мають координати, рівні відповідним компонентам трійок.
Дамо визначення основних понять.
· Адитивна трійка - трійка цілих чисел (a, b, c), де одне з чисел дорівнює сумі двох інших. Натуральной адитивної трійкою назвемо ту, в якій всі числа натуральні, уявної адитивної трійкою назвемо ту, в якій хоча б одне число недодатній.
· Похідна адитивної трійки першим і другим способом. Занумеруем змінні циклічно. Нехай в деякий момент i-1, i, i +1 - номери компонент трійки, отримані циклічної перестановкою номерів 1, 2, 3, причому такий, що число з номером i дорівнює сумі двох інших. Тоді її похідна «першим способом» - це трійка чисел, де числа з номерами i, i-1 залишаються незмінними, а число з номером i +1 замінюється на суму двох інших. Аналогічно, похідна другим способом - це та трійка, де числа з номерами i, i +1 залишаються незмінними, а число з номером i-1 замінюється на суму двох інших.
· Похідну першим способом від адитивної трійки T позначимо f (T), а похідну другим способом - g (T).
Наприклад, похідні від трійки (1, 2, 3) першим і другим способом відповідно - це трійки (5, 2, 3) і (1, 4, 3). При цьому трійки виду (p + q, p, q) назвемо адитивними трійками 1 роду, трійки виду (p, p + q, q) - адитивними трійками 2 роди, трійки виду (p, q, p + q) - відповідно адитивними трійками 3 роду.
· Найпростіші трійки - це адитивні трійки (2,1,1), (1,2,1) та (1,1,2)
· Безліч на k-тому ходу - це деяка множина, що складається з декількох адитивних трійок. Правила побудови цих множин будуть описані нижче. Кожна адитивна трійка є або найпростішої трійкою, або похідною від деякої іншої адитивної трійки.

1. Властивості послідовності
Побудуємо послідовність, і назвемо її тривимірною послідовністю Фібоначчі. Ця послідовність буде складатися з множин М _1, М _2, ... і так далі. Безліч М ₁ складається всього з однієї адитивної трійки (2,1,1). Далі будуємо послідовність наступним чином: Якщо адитивна трійка Т міститься в М _i, то її похідна першим способом міститься в М _{i +1,} а похідна другим способом міститься в М _{i +2.} Крім цього, безліч М ₂ доповнюється найпростішої трійкою (1, 2,1), а безліч М ₃ - відповідно найпростішої трійкою (1,1,2).
Зрозуміло, що при цьому адитивні трійки 1 роду лежать в множинах М _1, М _4, М _7, ..., М _{3 k +1,} ..., адитивні трійки 2 роди відповідно лежать в множинах М _2, М _5, М _8, ..., М _{3 k +2,} ..., і, нарешті трійки 3 роди - відповідно в множинах М _3, М _6, М _9, ..., М _{3 k,} ...
Нижче представлено схематичне зображення цієї послідовності, у вигляді таблиці:

Мн-во	Трійки												\| Mi \|
M ₁	(2,1,1)												1
M ₂	(2, 3, 1)						(1, 2, 1)						2
M ₃	(2, 3, 5)			(2, 1, 3)			(1, 2, 3)			(1, 1, 2)			4
M ₄	(8,3,5)	(4,3,1)			(4,1,3)		(3,2,1)		(5,2,3)			(3,1,2)	6
M ₅	(8,13,5)		(4,5,1)			(4,7,3)		(5,8,3)			(3,5,2)		10
	(2,7,5)		(2,5,3)			(3,4,1)		(1,4,3)			(1,3,2)
...	...												16

Зауважимо, що починаючи з n = 3, кількість елементів у безлічі M _i дорівнює i-того числа з послідовності Фібоначчі, помноженому на 2. (| M _i | = 2F _i).
Дійсно, кожна множина складається з похідних трійок попереднього множини, і попереднього за ним. Тому його потужність дорівнює сумі потужностей двох попередніх множин. Для n ³ 3 | M _i | = | M _{i -1} | + | M _{i -2} | (Під послідовністю Фібоначчі тут розуміється послідовність F _n, де F ₁ = F ₂ = 1, F _{i +2} = F _{i +1} + F _i, i> 1)
Номер тієї компоненти трійки, яка дорівнює сумі двох інших, відповідає залишку при діленні числа q на 3, де q - номер множини, в якому міститься дана трійка.

Властивості тривимірної послідовності Фібоначчі

Доведемо наступні дві теореми:
1. Всі числа адитивної трійки попарно взаємно прості.
2. Будь-яка адитивна трійка з взаємно простими компонентами входить в тривимірну послідовність Фібоначчі, причому рівно один раз.
Доказ (Теорема 1). Порахуємо найбільший загальний дільник будь-яких двох чисел в такій трійці. За алгоритмом Евкліда, він рівний найбільшому загальному дільнику в попередній адитивної трійці, з якої була утворена дана. Так як всі такі трійки, в кінцевому підсумку, утворюються з найпростіших трійок, в яких будь-які два числа взаємно прості, то в будь-трійці всі числа попарно взаємно прості. Теорема доведена.
Доказ (Теорема 2). Розіб'ємо теорему на два твердження. Перше твердження: «Ніяка трійка в послідовності не зустрінеться двічі». Друге твердження: «Будь-яка адитивна трійка з взаємно простими компонентами входить в тривимірну послідовність Фібоначчі».
Позначимо за

відношення між двома числами, сума яких утворює третє число адитивної трійки (для зручності відносини можна брати циклічно, наприклад, якщо сума стоїть на другому місці у трійці, то береться ставлення третього числа до першого, а якщо сума стоїть на першому місці, то розглядається відношення другого числа до третього). Оскільки числа адитивної трійки попарно взаємно прості, то λ можна вважати несократімой дробом. Для конкретної трійки M _a [b] відомий номер множини, в якому вона міститься, значить, можна сказати, на якому місці у трійці стоїть сума. Отже (так як числа взаємно прості), з несократімой дробу

можна відновити вихідну трійку. Тому далі замість адитивних трійок ми для зручності докази будемо писати лише число λ. Ясно, що якщо було виписано число λ, то в більш нижніх рядах будуть виписані числа

. Тепер доведемо вихідні твердження. Зрозуміло, що похідна «першим способом», тобто f (λ) дає трійку (

), А другим способом, тобто g (λ), дає трійку (

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

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

2. Упорядкування, обчислення елементів послідовності
Впорядкуємо елементи кожного безлічі наступним чином:
Для початку, i-тий елемент множини M _k будемо позначати М _k [i].
У першому безлічі знаходиться єдина адитивна трійка: М ₁ [1] = = (2,1,1).
f (М _a [b]) = M _{a +1} [b] (Перша похідна від адитивної трійки М _a [b] лежить в наступному безлічі, але індекс адитивної трійки зберігається.)
g (M _a [b]) = M _{a +2} [b + | M _{a +1} |] (Друга похідна від адитивної трійки лежить в безлічі «через одне», індекс збільшується на кількість елементів у множині М _{a +1.)}
Зобразимо це схематично (кожна адитивна трійка позначена точкою).

M ₁ [1]

M ₂ [1]

Отже, ми занумеровані, тобто впорядкували елементи кожного безлічі М _i. Визначимо для всіх a і b, для яких визначена адитивна трійка М _a [b], всі три її елемента.
Для початку знайдемо всі трійки виду M _a [1] (трійки першого стовпця). Обчислюючи результати перших трійок, помічаємо загальну закономірність і обчислюємо загальний вигляд.

M ₁ [1] = (2, 1, 1) = (F _3, F _1, F ₂₎	M _{3k +1} [1] = (F _{3k +3,} F _{3k +1,} F _{3k +2)}
M ₂ [1] = (2, 3, 1) = (F _3, F _4, F ₂₎	M _{3k +2} [1] = (F _{3k +3,} F _{3k +4,} F _{3k +2)}
M ₃ [1] = (2, 3, 5) = (F _3, F _4, F ₅₎	M _3k [1] = (F _3k, F _{3k +1,} F _{3k +2)}

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

3. Деякі залежності між уявними трійками
Тепер розширимо поняття M _a [b]. Визначимо її для всіх цілих a. Для цього введемо поняття «первісної».
Первообразной від адитивної трійки Т ₁ назвемо таку адитивну трійку Т _0, що похідна першим способом від неї дорівнює адитивної трійці Т _1. При цьому варто відзначити, що не кожна первообразная є натуральною трійкою, тобто не всі числа в первообразной натуральні.

Первісні від трійок вважаються за наступним правилом:

Аналогічним чином можна визначити «N разів похідну» і «N раз первісну» - це композиції N поспіль функцій або f, або g, або f _-1. Помістимо первісну від адитивної трійки M _a [b] у безліч M _{a -1,}
тобто f _-1 (M _a [b]) = M _{a -1} [b]. Таким чином, багатовимірна послідовність Фібоначчі визначена M _a [b] для всіх цілих b.
Тепер отриману 3х-мірну послідовність Фібоначчі можна зобразити так:
SHAPE \ * MERGEFORMAT

Отже, визначені всі адитивні трійки M _a [b], де b - натуральне, a ціле. Зокрема, розглянемо адитивні трійки виду M ₁ [i], тобто трійки, що перебувають у першому ряду.
Кожна така адитивна трійка має вигляд (x _i + y _i, x _i, y _i) і визначається двома числами: x _i і y _i.
Розглянемо послідовність Фібоначчі, в якій перші два числа рівні відповідно x _i і y _i, а кожне число, починаючи з третього, як і раніше дорівнює сумі двох попередніх. Знаючи числа x _i, y _{i i-того} стовпця можна обчислити всі адитивні трійки в цьому стовпці, по аналогії з першим стовпцем.
Отже, мають місце такі рівності:

M _{3k +1} [i] = (F _{3k +3,} F _{3k +1,} F _{3k +2)}	M ₁ [i] = (x _i + y _i, x _i, y _i)
M _{3 k +2} [i] = (F _{3 k +3,} F _{3 k +4,} F _{3 k +2)}	F ₁ = x _i, F ₂ = y _i
M _{3 k} [i] = (F _{3 k,} F _{3 k +1,} F _{3 k +2)}	F _{n +2} = F _{n +1} + F _n

Зрозуміло, що якщо ми знайдемо перше адитивну трійку деякого стовпця, то зможемо обчислити і всі інші трійки цього стовпця. Нижче записані перші трійки стовпців з номерами від 1 до 10.
M1 [1] = (2, 1, 1)
M1 [2] = (1, 0, 1)
M1 [3] = (2, 3, -1)
M1 [4] = (1, 1, 0)
M1 [5] = (-2, -7, 5)
M1 [6] = (-1, 4, 3)
M1 [7] = (8, 19, -11)
M1 [8] = (5, 12, -7)
M1 [9] = (4, 9, -5)
M1 [10] = (3, 7, -4)

Нижче викладено алгоритм по знаходженню спільної члена послідовності. Для початку визначимо ряд Фібоначчі для всіх цілих чисел. F _{- n} = (-1) ^{n +1} F _n.
Далі визначимо формулу для «N раз похідної» (ця ж формула виконується для «N раз первообразной»)
Нехай вихідна трійка має вигляд:

Тоді її похідні дорівнюють:

Тепер обчислимо всі елементи першого рядка рекуррентно, але з маленьким числом дій.
SHAPE \ * MERGEFORMAT

1 2 3 4 5 6 7 8 9 10

l _F (8) = 5

Багатовимірні послідовності Фібоначчі

Література

Введення, основні поняття

Властивості тривимірної послідовності Фібоначчі

Деякі залежності між уявними трійками

4. Практичне застосування

4.1 Рішення завдання «Математики грають»

4.2 Фігури в декартових системах координат, з вершинами в координатах, рівних числах трійки

Напрямки для досліджень

Література