Обобщённые числа Фибоначчи
Шаблон:Нет определения Числа Фибоначчи образуют определённую с помощью рекурсии последовательность
- для целого числа .
То есть, начиная с двух начальных значений, каждое число равно сумме двух предшествующих.
Последовательность Фибоначчи интенсивно изучена и обобщена многими способами, например, начиная последовательность с других чисел, отличных от 0 или 1, или путём сложения более двух предшествующих чисел для образования следующего числа. Данная статья описывает различные расширения и обобщения чисел Фибоначчи.
Расширение на отрицательные числа
Если использовать рекурсию , можно расширить числа Фибоначчи на отрицательные числа. Мы получаем:
- … −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, …
с формулой общего члена .
См. также Негафибоначчиевы числа.
Расширение на вещественные и комплексные числа
Существует много возможных обобщений, которые расширяют числа Фибоначчи на вещественные числа (а иногда и на комплексные числа). Они используют золотое сечение Шаблон:Mvar и базируются на формуле Бине
Аналитическая функция
имеет свойство, что для чётных целых чисел Шаблон:Mvar[1]. Аналогично, для аналитической функции
выполняется для всех нечётных целых чисел Шаблон:Mvar.
Собирая всё вместе, получим аналитическую функцию
для которой выполняется для всех целых чисел Шаблон:Mvar[2].
Поскольку для всех комплексных чисел Шаблон:Mvar, эта функция даёт также расширение последовательности Фибоначчи для всей комплексной плоскости. Таким образом, мы можем вычислить обобщённую функцию Фибоначчи для комплексной переменной, например,
Векторное пространство
Термин последовательности Фибоначи может быть применен для любой функции Шаблон:Mvar, отображающей целочисленную переменную в некоторое поле, для которой . Эти функции в точности являются функциями вида , так что последовательности Фибоначчи образуют векторное пространство, базисом которого являются функции и .
В качестве области определения функции Шаблон:Mvar может быть взята любая абелева группа (рассматриваемая как [[Модуль над кольцом|Шаблон:Mvar-модуль]]). Тогда последовательности Фибоначчи образуют 2-мерный Шаблон:Mvar-модуль.
Похожие целые последовательности
Целые последовательности Фибоначчи
2-мерный Шаблон:Mvar-модуль последовательностей целых чисел Фибоначчи состоит из всех целых последовательностей, удовлетворяющих соотношению . Если выразить в терминах двух первых начальных значений, получим
где Шаблон:Mvar — золотое сечение.
Отношение между двумя последовательными элементами сходится к золотому сечению, за исключением случая последовательности, которая состоит из нулей и последовательностей, в которых отношение двух первых членов равно .
Последовательность можно записать в виде
в которой тогда и только тогда, когда . В таком виде простейшим нетривиальным примером является и эта последовательность состоит из чисел Люка:
Мы имеем и . Выполняется:
Любая нетривиальная последовательность целых чисел Фибоначчи (возможно, после сдвига на конечное число позиций) является одной из строк таблицы Витхоффа. Сама последовательность Фибоначчи является первой строкой, а сдвинутая последовательность Люка является второй строкойШаблон:Sfn.
См. также [[Период Пизано|Последовательности чисел Фибоначчи по модулю Шаблон:Mvar]].
Последовательности Люка
Другое обобщение последовательностей Фибоначчи — последовательности Люка, определённые следующим образом:
- ,
- ,
- ,
где обычная последовательность Фибоначчи является частным случаем с и . Другая последовательность Люка начинается с , . Такие последовательности имеют приложение в теории чисел и проверке простоты.
В случае, когда , эта последовательность называется Шаблон:Mvar-последовательностью Фибоначчи. Например, последовательность Пелля называется также 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
Шаблон:Mvar-константа Фибоначчи — значение, к которому стремится отношение смежных чисел Шаблон:Mvar-последовательности Фибоначчи. Она называется также Шаблон:Mvar-м отношением ценного металла и является единственным положительным корнем уравнения . Например, в случае константа равна , или золотому сечению, а в случае константа равна 1 + Шаблон:Sqrt, или серебряному сечению. Для общего случая Шаблон:Mvar-константа равна .
В общем случае можно называть - последовательностью Фибоначчи, а можно назвать -последовательностью Люка.
(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
Числа Фибоначчи высокого порядка
Последовательность Фибоначчи порядка Шаблон:Mvar — это последовательность целых чисел, в которой каждый элемент является суммой предыдущих Шаблон:Mvar элементов (за исключением первых Шаблон:Mvar элементов последовательности). Обычные числа Фибоначчи имеют порядок 2. Случаи и тщательно исследованы. Число разложений неотрицательных целых чисел на части, не превосходящие Шаблон:Mvar, является последовательностью Фибоначчи порядка Шаблон:Mvar. Последователь количеств строк из 0 и 1 длины Шаблон:Mvar, содержащих не более Шаблон:Mvar последовательных нулей, также является последовательностью Фибоначчи порядка Шаблон:Mvar.
Эти последовательности, их границы отношений членов и их пределы отношений членов исследовал Шаблон:Не переведено 5 в 1913Шаблон:Sfn.
Числа трибоначчи
Числа трибоначчи похожи на числа Фибоначчи, но вместо двух предопределённых чисел последовательность начинается с трёх чисел и каждый следующий член является суммой предыдущих трёх:
- 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (Шаблон:OEIS)
Постоянная трибоначчи
является значением, к которому стремится отношение двух соседних чисел трибоначчи. Число является корнем многочлена , а также удовлетворяет уравнению . Постоянная трибоначчи важна для изучения плосконосого куба.
Величина, обратная постоянной трибоначчи, выраженная отношением , может быть записана как:
Числа трибоначчи задаются также формулой[3]
- ,
где Шаблон:Math означает Шаблон:Не переведено 5 и
- .
Числа тетраначчи
Числа тетраначчи начинаются с четырёх предопределённых членов, а каждый следующий член вычисляется как сумма предыдущих четырёх членов последовательности. Первые несколько чисел тетраначчи:
- 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)
Постоянная тетраначчи — это значение, к которому стремится отношение соседних членов последовательности тетраначчи. Эта постоянная является корнем многочлена , примерно равна 1,927561975482925 Шаблон:OEIS2C и удовлетворяет уравнению .
Константа тетраначчи выражается в терминах радикаловШаблон:Sfn
где
Более высокие порядки
Были вычислены числа пентаначчи (5 порядка), гексаначчи (6 порядка) и гептаначчи (7 порядка).
Числа пентаначчи (5 порядка):
- 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, … Шаблон:OEIS
Числа гексаначчи (6 порядка):
- 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, … Шаблон:OEIS
Числа гептаначчи (7 порядка):
- 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … Шаблон:OEIS
Числа октаначчи (8 порядка):
- 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, … Шаблон:OEIS
Числа ноначчи (9 порядка):
- 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
Предел отношения последовательных членов последовательности Шаблон:Mvar-наччи стремится к корню уравнения (Шаблон:OEIS2C, Шаблон:OEIS2C, Шаблон:OEIS2C).
Альтернативная рекурсивная формула предела отношения Шаблон:Mvar двух последовательных чисел Шаблон:Mvar-наччи
- .
Частный случай является традиционной последовательностью Фибоначчи и даёт золотое сечение .
Вышеприведённые формулы для отношения выполняются для последовательностей Шаблон:Mvar-наччи, сгенерированных из произвольных чисел. Предел этого отношения равен 2 при Шаблон:Mvar, стремящемся к бесконечности. Последовательность чисел «бесконечно-наччи», если её попытаться описать, должна начинаться с бесконечного числа нулей, после чего должна идти последовательность
- […, 0, 0, 1,] 1, 2, 4, 8, 16, 32, …,
то есть просто степени двойки.
Предел последовательности для любого является положительным корнем Шаблон:Mvar характеристического уравненияШаблон:Sfn
Корень Шаблон:Mvar находится в интервале . Отрицательный корень характеристического уравнения находится в интервале (−1, 0), если Шаблон:Mvar чётно. Этот корень и каждый комплексный корень характеристического уравнения имеет модуль Шаблон:Sfn.
Последовательность для положительного корня Шаблон:Mvar для любого Шаблон:Sfn
Не существует решения характеристического уравнения в терминах радикалов, если Шаблон:Sfn.
Шаблон:Mvar-й элемент последовательности Шаблон:Mvar-наччи задаётся формулой
где Шаблон:Math означает ближайшее целое, а Шаблон:Mvar — константа Шаблон:Mvar-наччи, которая является корнем , ближайшим к 2[4].
Задача подбрасования монеты связана с последовательностью Шаблон:Mvar-наччи. Вероятность, что не выпадет Шаблон:Mvar раз последовательно решка в Шаблон:Mvar бросаниях идеальной монеты, равна [5].
Слово Фибоначчи
Шаблон:Main По аналогии числовому аналогу слово Фибоначчи определяется как
где + означает конкатенацию двух строк. Последовательность строк Фибоначчи начинается с
- b, a, ab, aba, abaab, abaababa, abaababaabaab, … Шаблон:OEIS
Длина каждой строки Фибоначчи равна числу Фибоначчи и для каждого числа Фибоначчи существует строка Фибоначчи.
Строки Фибоначчи оказываются для некоторых алгоритмов входными данными наихудшего случая.
Если «a» и «b» представляют два различных материала или длины атомных связей, структура, соответствующая строке Фибоначчи, является Шаблон:Не переведено 5, непериодической квазикристаллической структурой с необычными спектральными свойствами.
Свёрнутые последовательности Фибоначчи
Свёрнутая последовательность Фибоначчи получается путём применения операции свёртки к последовательности Фибоначчи один и более раз. ОпределимШаблон:Sfn:
и
Первые несколько последовательностей
- r = 1: 0, 0, 1, 2, 5, 10, 20, 38, 71, … Шаблон:OEIS2C.
- r = 2: 0, 0, 0, 1, 3, 9, 22, 51, 111, … Шаблон:OEIS2C.
- r = 3: 0, 0, 0, 0, 1, 4, 14, 40, 105, … Шаблон:OEIS2C.
Последовательности можно вычислить с помощью рекуррентной формулы
Производящая функция Шаблон:Mvar-ой свёртки равна
Последовательности связаны с последовательностью Шаблон:Не переведено 5 отношением
где является Шаблон:Mvar-ой производной . Эквивалентно, является коэффициентом , если развернуть как сумму степеней .
Первая свёртка может быть записана в терминах чисел Фибоначчи и Люка
и удовлетворяет рекуррентному соотношению
Аналогичное выражение можно найти для Шаблон:Math с возрастающей сложностью по мере роста Шаблон:Mvar. Числа являются суммами по строкам треугольника Хосоя.
Как и для чисел Фибоначчи, существуют некоторые комбинаторные интерпретации этих последовательностей. Например, является количеством способов записать Шаблон:Math в виде упорядоченной суммы чисел 0, 1 и 2, при этом 0 используется ровно один раз. В частности, и, соответственно, 4 — 2 = 2 можно записать как Шаблон:Nowrap, Шаблон:Nowrap, Шаблон:Nowrap, Шаблон:Nowrap, Шаблон:Nowrap.[6]
Другие обобщения
Шаблон:Не переведено 5 являются другим обобщением чисел Фибоначчи.
Последовательность Падована образована рекуррентным соотношением .
Случайная последовательность Фибоначчи может быть определена как бросание монеты для каждой позиции n последовательности и выбора в случае выпадения орла и в случае решки. Согласно работе Фурстенберга и Кестена эта последовательность почти достоверно растёт экспоненциально с постоянной скоростью. Константа скорости роста была вычислена в 1999 Дивакаром Висванатом и известна как «Шаблон:Не переведено 5».
Репфигит, или число Кита, это целое число, которое получается в результате последовательности Фибоначчи, начинающейся с последовательности чисел, представляющей последовательность цифр числа. Например, для числа 47, последовательность Фибоначчи начинается с 4 и 7 и содержит 47 в качестве шестого члена (Шаблон:Nowrap). Число Кита может быть получено как последовательность трибоначчи, если оно содержит 3 знака, как последовательность тетраначчи, если число содержит 4 знака и т. д.. Несколько первых чисел Кита:
- 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, … Шаблон:OEIS
Поскольку множество последовательностей, удовлетворяющих соотношению , замкнуто относительно поэлементного сложения и умножения на константу, его можно рассматривать как векторное пространство. Любая такая последовательность однозначно определяется выбором двух элементов, так что векторное пространство является двумерным. Если обозначить такую последовательность через (первые два члена последовательности), числа Фибоначчи и сдвинутые числа Фибоначчи , будут каноническим базисом этого пространства
для всех таких последовательностей Шаблон:Mvar. Например, если Шаблон:Mvar — это последовательность Люка Шаблон:Nowrap, мы имеем
- .
Шаблон:Mvar-генерированная последовательность Фибоначчи
Мы можем определить Шаблон:Mvar-генерированную последовательность Фибоначчи (где Шаблон:Mvar — положительное рациональное число).
Если
где Шаблон:Mvar — это Шаблон:Mvar-ое простое число, мы определяем
Если , полагаем , а в случае , полагаем .
Последовательность Шаблон:Mvar Последовательность OEIS Последовательность Фибоначчи 6 Шаблон:OEIS2C Последовательность Пелля 12 Шаблон:OEIS2C Последовательность Якобсталя 18 Шаблон:OEIS2C Последовательность трибоначчи 30 Шаблон:OEIS2C Последовательность тетраначчи 210 Шаблон:OEIS2C Последовательность Падована 15 Шаблон:OEIS2C
Полуфибоначчиева последовательность
Полуфиббоначиева последовательность (Шаблон:OEIS2C) определяется посредством той же рекуррентной формулы для членов с нечётными индексами и , но для чётных индексов берётся , . Выделенные нечётные члены (Шаблон:OEIS2C) удовлетворяют уравнению и строго возрастают. Они дают множество полуфибоначчиевых чисел
- 1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, 53, 69, 70, 87, 93, 116, 119, 145, 154, … Шаблон:OEIS,
для которых верна формула .