Узагальнення чисел Фібоначчі

У математиці, число Фібоначчі є формою послідовності, що рекурсивно визначається як:

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2), для цілих n > 1.

Так, кожен елемент, окрім перших двох, є сумою двох попередніх елементів послідовності.

Послідовність Фібоначчі досліджувалася протягом тривалого часу, тому для неї було знайдено декілька узагальнень, наприклад, використання чисел, відмінних від 0 та 1 на початку, додавання більше ніж двох чисел для знаходження наступного елемента, або додавання замість звичайних чисел певних об'єктів.

Узагальнення для від'ємних цілих чисел

Використовуючи F_n-2 = F_n — F_n-1, можна розширити послідовність Фібоначчі для від'ємних цілих чисел. Таким чином, отримаємо: … -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, … та F_-n = -(-1)ⁿF_n.

Узагальнення для всіх дійсних та комплексних чисел

Існує декілька узагальнень чисел Фібоначчі, які дозволяють генерувати послідовності дійсних чисел (та інколи комплексних чисел). Вони включають золотий перетин $\phi$, та базуються на формулі Бінета:

$F_n=\frac{{\phi }^n-(-\phi {)}^{-n}}{\sqrt{5}}.$

Аналітична функція

$Fe(x)=\frac{{\phi }^x-{\phi }^{-x}}{\sqrt{5}}$

має властивість Fe(n) = F_n для парних n. Подібним чином, аналітична функція:

$Fo(x)=\frac{{\phi }^x+{\phi }^{-x}}{\sqrt{5}}$

задовольняє Fo(n) = F_n для непарних n.

І нарешті, склавши разом попередні два вирази, отримуємо аналітичну функцію

$Fib(x)=\frac{{\phi }^x-\cos (x\pi ){\phi }^{-x}}{\sqrt{5}}$

яка задовольняє Fib(n)=F_n для всіх цілих чисел n.

Оскільки Fib(x+2) = Fib(x+1) + Fib(x) для всіх комплексних x, ця функція також надає розширення послідовності Фібоначчі на всю комплексну площину. Таким чином, можна знайти узагальнену функцію Фібоначчі, що поширюється на комплексні числа, наприклад,

$Fib(3+4i)\approx -5248.5-14195.9i$

Векторний простір

Термін Послідовність Фібоначчі можна застосувати більш узагальнено для функції g з цілих чисел на площину g(n+2) = g(n) + g(n+1). Ці функції мають таку ж форму, як g(n) = F(n)g(1) + F(n-1)g(0), отже послідовність Фібоначчі є однією з форм векторного простору з функціями F(n) та F(n-1) у ролі базису.

Більш загально, діапазон g можна взяти так, що він буде будь-якою з Абелевих груп (які також згадуються, як Модуль над кільцем). Тоді послідовності Фібоначчі аналогічно формують 2-вимірний Z-модуль.

Подібні цілочисельні послідовності

Цілочисельна послідовність Фібоначчі

Двовимірний Z-модуль цілочисельної послідовності Фібоначчі складається з усіх цілочисельних послідовностей, що задовольняють g(n+2) = g(n) + g(n+1). Виразивши це через два початкові значення, маємо:

g(n) = F(n)g(1) + F(n-1)g(0) = $g(1)\frac{{\phi }^n-(-\phi {)}^{-n}}{\sqrt{5}}+g(0)\frac{{\phi }^{n-1}-(-\phi {)}^{1-n}}{\sqrt{5}},$

де $\phi$ є золотим перетином.

Співвідношення між двома послідовними елементами сходиться до золотої пропорції, за винятком випадків, коли послідовність складається з нулів, та випадків, коли співвідношення між першими двома елементами становить $(-\phi {)}^{-1}$.

Послідовність може бути записана, як

$a{\phi }^n+b(-\phi {)}^{-n},$

де a = 0 тільки якщо b = 0. У такій формі, найпростішим не-тривіальним прикладом є a = b = 1, що є послідовністю чисел Люка:

$L_n={\phi }^n+(-\phi {)}^{-n}.$

Маємо L(1) = 1 та L(2) = 3. Властивості включають:

${\phi }^n={\left(\frac{1}{2}(1+\sqrt{5})\right)}^n=\frac{1}{2}(L(n)+F(n)\sqrt{5}),$

$L\left(n\right)=F(n-1)+F(n+1).$

Кожна нетривіальна послідовність Фібоначчі виникає (можливо після зсуву на скінченне число позицій) як один з рядків Every nontrivial Fibonacci integer sequence appears (possibly after a shift by a finite number of positions) as one of the rows of the Таблиці Вітхоффа. Сама послідовність Фібоначчі є першим рядком, а зсуви послідовності Люка є другим рядком.

Послідовності Люка

Різні узагальнення послідовності Фібоначчі є видом Послідовностей Люка, формулу якого наведено нижче:

U(0) = 0,

U(1) = 1,

U(n + 2) = PU(n + 1) − QU(n), де звичайна послідовність Фібоначчі є особливим випадком, коли P = 1 та Q = −1. Інший вид послідовності Люка починається з V(0) = 2, V(1) = P. Такі послідовності мають застосування у теорії чисел та доведеннях простих чисел.

При Q = −1, послідовність називається P-послідовністю Фібоначчі, наприклад, послідовність Пелля також називається 2-послідовністю Фібоначчі.

3-послідовністю Фібоначчі є

0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, … Шаблон:OEIS

4-послідовністю Фібоначчі є

0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, … Шаблон:OEIS

5-послідовністю Фібоначчі є

0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, … Шаблон:OEIS

6-послідовністю Фібоначчі є

0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, … Шаблон:OEIS

n-стала Фібоначчі це співвідношення, до якого прямує відповідна n-послідовність Фібоначчі і це єдиний додатній корінь з x² − nx − 1 = 0. Наприклад, у випадку, коли n = 1 це $\frac{1+\sqrt{5}}{2}$, або золотий перетин, а у випадку, коли n = 2 це $1+\sqrt{2}$, або срібний перетин. У загальному випадку, для деякого n це $\frac{n+\sqrt{n^2+4}}{2}$.Шаблон:Citation needed

У загальному, U(n) можна назвати (P,-Q)-послідовністю Фібоначчі, а V(n) можна назвати (P,-Q)-послідовністю Люка.

(1,2)-послідовність Фібоначчі це

0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, … Шаблон:OEIS

(1,3)-послідовність Фібоначчі це

1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, … Шаблон:OEIS

(2,2)-послідовність Фібоначчі це

0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, … Шаблон:OEIS

(3,3)-послідовність Фібоначчі це

0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, 507627, 1924560, 7296561, 27663363, 104879772, 397629405, 1507527531, 5715470808, … Шаблон:OEIS

Числа Фібоначчі вищих порядків

Послідовністю Фібоначчі n порядку є цілочисельна послідовність, у якій кожен елемент є сумою попередніх n елементів (за винятком перших n елементів послідовності). Звичайні числа Фібоначчі є послідовністю Фібоначчі 2 порядку. Випадки n=3 та n=4 були ретельно досліджені. Кількість композицій невід'ємних цілих чисел на частини, не менші ніж n є послідовністю Фібоначчі n порядку.

Числа трібоначчі

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

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … Шаблон:OEIS

Сталою трібоначчі є $\frac{1+\sqrt[3]{19+3\sqrt{33}}+\sqrt[3]{19-3\sqrt{33}}}{3}$ ≈ 1.839286755, це стала, до якої прямують співвідношення між двома сусідніми елементами послідовності. Це число є коренем x³ − x² − x − 1, approximately 1.839286755214161 Шаблон:OEIS, а також задовольняє рівняння x + x⁻³ = 2. Цей факт є важливим при вивченні кирпатого куба.

Числа тетраначчі

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

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, … Шаблон:OEIS

Константою тетраначчі називають число, до якого прямує співвідношення між сусідніми елементами послідовності тетраначчі. Воно є коренем поліному x⁴ − x³ − x² − x − 1, approximately 1.927561975482925 Шаблон:OEIS2C, а також задовольняє рівняння x + x⁻⁴ = 2.

Вищі порядки

Було обчислено пентаначчі, гексаначчі та гептаначчі. Послідовність пентаначчі має такий вигляд:

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, … Шаблон:OEIS

Послідовність гексаначчі:

0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, … Шаблон:OEIS

Послідовність гептаначчі:

0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … Шаблон:OEIS

Послідовність октаначчі:

0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, … Шаблон:OEIS

Послідовність ноначчі:

0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, … Шаблон:OEIS

Границя співвідношення кожного наступного елемента послідовностей n-наччі прямує до кореня рівняння $x+x^{-n}=2$ (Шаблон:OEIS, Шаблон:OEIS, Шаблон:OEIS).

Альтернативною рекурсивною формулою для границі співвідношення r двох послідовних чисел з послідовності n-наччі є $r=\sum _{k=0}^{n-1}{r}^{-k}$.

Особливий випадок n = 2 є традиційною послідовністю Фібоначчі, що створює золотий перетин $\varphi =1+\frac{1}{\varphi }$.

Див. також

• Послідовність Фібоначчі
• Золотий перетин
• Число Люка
• Куб Фібоначчі

Посилання

• Шаблон:Springer