Обобщения чисел Фибоначчи

Математические последовательности

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

${\displaystyle F_{n}={\begin{cases}0&n=0\\1&n=1\\F_{n-1}+F_{n-2}&n>1\end{cases}}}$

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

Последовательность Фибоначчи была тщательно изучена и обобщена многими способами, например, начиная с чисел, отличных от 0 и 1, добавляя более двух чисел для получения следующего числа или добавляя объекты, отличные от чисел.

Расширение на отрицательные целые числа

Используя , можно расширить числа Фибоначчи до отрицательных целых чисел . Итак, получаем: ${\displaystyle F_{n-2}=F_{n}-F_{n-1}}$

... −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, ...

и . ^[1] ${\displaystyle F_{-n}=(-1)^{n+1}F_{n}}$

См. также Негафибоначчиевое кодирование .

Расширение на все действительные или комплексные числа

Существует ряд возможных обобщений чисел Фибоначчи, которые включают действительные числа (а иногда и комплексные числа ) в их области. Каждое из них включает золотое сечение φ и основано на формуле Бине

${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}$

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

${\displaystyle \operatorname {Fe} (x)={\frac {\varphi ^{x}-\varphi ^{-x}}{\sqrt {5}}}}$

имеет свойство, что для четных целых чисел . ^[2] Аналогично, аналитическая функция: ${\displaystyle \operatorname {Fe} (n)=F_{n}}$ ${\displaystyle n}$

${\displaystyle \operatorname {Fo} (x)={\frac {\varphi ^{x}+\varphi ^{-x}}{\sqrt {5}}}}$

удовлетворяет для нечетных целых чисел . ${\displaystyle \operatorname {Fo} (n)=F_{n}}$ ${\displaystyle n}$

Наконец, собрав все это вместе, получим аналитическую функцию

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

удовлетворяет для всех целых чисел . ^[3] ${\displaystyle \operatorname {Fib} (n)=F_{n}}$ ${\displaystyle n}$

Так как для всех комплексных чисел эта функция также обеспечивает расширение последовательности Фибоначчи на всю комплексную плоскость. Следовательно, мы можем вычислить обобщенную функцию Фибоначчи комплексной переменной, например, ${\displaystyle \operatorname {Fib} (z+2)=\operatorname {Fib} (z+1)+\operatorname {Fib} (z)}$ ${\displaystyle z}$

${\displaystyle \operatorname {Fib} (3+4i)\approx -5248.5-14195.9i}$

Вектор пространства

Термин последовательность Фибоначчи также применяется в более общем смысле к любой функции от целых чисел до поля , для которого . Эти функции являются в точности функциями вида , поэтому последовательности Фибоначчи образуют векторное пространство с функциями и в качестве базиса . ${\displaystyle g}$ ${\displaystyle g(n+2)=g(n)+g(n+1)}$ ${\displaystyle g(n)=F(n)g(1)+F(n-1)g(0)}$ ${\displaystyle F(n)}$ ${\displaystyle F(n-1)}$

В более общем случае диапазон может быть взят как любая абелева группа (рассматриваемая как Z - модуль ). Тогда последовательности Фибоначчи образуют 2-мерный Z -модуль таким же образом. ${\displaystyle g}$

Похожие целочисленные последовательности

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

Двумерный -модуль целочисленных последовательностей Фибоначчи состоит из всех целочисленных последовательностей, удовлетворяющих . Выражаясь через два начальных значения, имеем: ${\displaystyle \mathbb {Z} }$ ${\displaystyle g(n+2)=g(n)+g(n+1)}$

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

где находится золотое сечение. ${\displaystyle \varphi }$

Соотношение между двумя последовательными элементами сходится к золотому сечению, за исключением случая последовательности, которая постоянно равна нулю, и последовательностей, где отношение двух первых членов равно . ${\displaystyle (-\varphi )^{-1}}$

Последовательность можно записать в виде

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

в котором тогда и только тогда, когда . В этой форме простейший нетривиальный пример имеет , который является последовательностью чисел Люка : ${\displaystyle a=0}$ ${\displaystyle b=0}$ ${\displaystyle a=b=1}$

${\displaystyle L_{n}=\varphi ^{n}+(-\varphi )^{-n}.}$

У нас есть и . Свойства включают в себя: ${\displaystyle L_{1}=1}$ ${\displaystyle L_{2}=3}$

${\displaystyle {\begin{aligned}\varphi ^{n}&=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{\!n}={\frac {L(n)+F(n){\sqrt {5}}}{2}},\\L(n)&=F(n-1)+F(n+1).\end{aligned}}}$

Каждая нетривиальная целочисленная последовательность Фибоначчи появляется (возможно, после сдвига на конечное число позиций) как одна из строк массива Витхоффа . Сама последовательность Фибоначчи является первой строкой, а сдвиг последовательности Лукаса является второй строкой. ^[4]

См. также последовательности целых чисел Фибоначчи по модулю n .

Сцены Лукаса

Другим обобщением последовательности Фибоначчи являются последовательности Люка , определяемые следующим образом:

${\displaystyle {\begin{aligned}U(0)&=0\\U(1)&=1\\U(n+2)&=PU(n+1)-QU(n),\end{aligned}}}$

где нормальная последовательность Фибоначчи является частным случаем и . Другой вид последовательности Люка начинается с , . Такие последовательности имеют приложения в теории чисел и доказательстве простоты . ${\displaystyle P=1}$ ${\displaystyle Q=-1}$ ${\displaystyle V(0)=2}$ ${\displaystyle V(1)=P}$

Когда эта последовательность называется P -последовательностью Фибоначчи , например, последовательность Пелля также называется 2-последовательностью Фибоначчи . ${\displaystyle Q=-1}$

Последовательность 3-Фибоначчи :

0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, ... (последовательность A006190 в OEIS )

Последовательность 4-Фибоначчи :

0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, ... (последовательность A001076 в OEIS )

Последовательность 5-Фибоначчи :

0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275, 13741001, 71351280, 370497401, 1923838285, 9989688826, ... (последовательность A052918 в OEIS )

Последовательность 6-Фибоначчи :

0, 1, 6, 37, 228, 1405, 8658, 53353, 328776, 2026009, 12484830, 76934989, 474094764, 2921503573, 18003116202, ... (последовательность A005668 в OEIS )

Константа n -Фибоначчи - это отношение, к которому стремятся соседние -числа Фибоначчи; его также называют n -м металлическим средним , и это единственный положительный корень . Например, случай - это , или золотое сечение , и случай - это , или серебряное сечение . Как правило, случай - это . ^{[ необходима цитата ]} ${\displaystyle n}$ ${\displaystyle x^{2}-nx-1=0}$ ${\displaystyle n=1}$ ${\displaystyle {\frac {1+{\sqrt {5}}}{2}}}$ ${\displaystyle n=2}$ ${\displaystyle 1+{\sqrt {2}}}$ ${\displaystyle n}$ ${\displaystyle {\frac {n+{\sqrt {n^{2}+4}}}{2}}}$

В общем случае можно назвать ( P , −Q ) -последовательностью Фибоначчи , а V ( n ) можно назвать ( P , −Q ) -последовательностью Люка . ${\displaystyle U(n)}$

Последовательность (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, ... (последовательность A001045 в 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, ... (последовательность A006130 в OEIS )

Последовательность (2,2)-Фибоначчи :

0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, ... (последовательность A002605 в OEIS )

Последовательность (3,3)-Фибоначчи :

0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893, 507627, 1924560, 7296561, 27663363, 104879772, 397629405, 1507527531, 5715470808, ... (последовательность A030195 в OEIS )

Числа Фибоначчи высшего порядка

Последовательность Фибоначчи порядка n — это целочисленная последовательность, в которой каждый элемент последовательности является суммой предыдущих элементов (за исключением первых элементов последовательности). Обычные числа Фибоначчи — это последовательность Фибоначчи порядка 2. Случаи и были тщательно исследованы. Количество композиций неотрицательных целых чисел на части, которые не более, является последовательностью Фибоначчи порядка . Последовательность количества строк из нулей и единиц длины , которые содержат не более последовательных нулей, также является последовательностью Фибоначчи порядка . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n=3}$ ${\displaystyle n=4}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n}$

Эти последовательности, их предельные соотношения и предел этих предельных соотношений были исследованы Марком Барром в 1913 году. ^[5]

Числа Трибоначчи

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

, , 1 , 1 , 2 , 4 , 7 , 13 , 24 , 44 , 81 , 149 , 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (последовательность A000073 в OEIS )

Серия была впервые формально описана Агрономом ^[6] в 1914 году, ^[7] но ее первое непреднамеренное использование относится к « Происхождению видов» Чарльза Р. Дарвина . В примере иллюстрации роста популяции слонов он опирался на расчеты, сделанные его сыном, Джорджем Х. Дарвином . ^[8] Термин трибоначчи был предложен Файнбергом в 1963 году. ^[9]

Константа трибоначчи

${\displaystyle {\frac {1+{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}}{3}}={\frac {1+4\cosh \left({\frac {1}{3}}\cosh ^{-1}\left(2+{\frac {3}{8}}\right)\right)}{3}}\approx 1.839286755214161,}$(последовательность A058265 в OEIS )

— это отношение, к которому стремятся соседние числа трибоначчи. Это корень многочлена , а также удовлетворяет уравнению . Это важно при изучении плосконосого куба . ${\displaystyle x^{3}-x^{2}-x-1=0}$ ${\displaystyle x+x^{-3}=2}$

Геометрическое построение постоянной Трибоначчи (AC) с помощью циркуля и размеченной линейки по методу, описанному Ксерардо Нейрой.

Обратная величина постоянной трибоначчи , выраженная соотношением , может быть записана как: ${\displaystyle \xi ^{3}+\xi ^{2}+\xi =1}$

${\displaystyle \xi ={\frac {{\sqrt[{3}]{17+3{\sqrt {33}}}}-{\sqrt[{3}]{-17+3{\sqrt {33}}}}-1}{3}}={\frac {3}{1+{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}}}\approx 0.543689012.}$(последовательность A192918 в OEIS )

Числа трибоначчи также определяются формулой ^[10]

${\displaystyle T(n)=\left\lfloor 3b\,{\frac {\left({\frac {1}{3}}\left(a_{+}+a_{-}+1\right)\right)^{n}}{b^{2}-2b+4}}\right\rceil }$

где обозначает ближайшую целую функцию и ${\displaystyle \lfloor \cdot \rceil }$

${\displaystyle {\begin{aligned}a_{\pm }&={\sqrt[{3}]{19\pm 3{\sqrt {33}}}}\,,\\b&={\sqrt[{3}]{586+102{\sqrt {33}}}}\,.\end{aligned}}}$

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

Числа тетраначчи начинаются с четырех предопределенных членов, каждый последующий член является суммой предыдущих четырех членов. Первые несколько чисел тетраначчи:

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, … (последовательность A000078 в OEIS )

Константа тетраначчи — это отношение, к которому стремятся соседние числа тетраначчи. Это корень многочлена , приблизительно 1,927561975482925 (последовательность A086088 в OEIS ), а также удовлетворяет уравнению . ${\displaystyle x^{4}-x^{3}-x^{2}-x-1=0}$ ${\displaystyle x+x^{-4}=2}$

Константу тетраначчи можно выразить через радикалы следующим выражением: ^[11]

${\displaystyle x={\frac {1}{4}}\!\left(1+{\sqrt {u}}+{\sqrt {11-u+{\frac {26}{\sqrt {u}}}}}\,\right)}$

где,

${\displaystyle u={\frac {1}{3}}\left(11-56{\sqrt[{3}]{\frac {2}{-65+3{\sqrt {1689}}}}}+2\cdot 2^{\frac {2}{3}}{\sqrt[{3}]{-65+3{\sqrt {1689}}}}\right)}$

и является действительным корнем кубического уравнения ${\displaystyle u}$ ${\displaystyle u^{3}-11u^{2}+115u-169.}$

Высшие порядки

Были вычислены числа пентаначчи, гексаначчи, гептаначчи, октаначчи и эннеаначчи.

Числа Пентаначчи:

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, … (последовательность A001591 в OEIS )

Константа пентаначчи — это отношение, к которому стремятся соседние числа пентаначчи. Это корень многочлена , приблизительно 1,965948236645485 (последовательность A103814 в OEIS ), а также удовлетворяет уравнению . ${\displaystyle x^{5}-x^{4}-x^{3}-x^{2}-x-1=0}$ ${\displaystyle x+x^{-5}=2}$

Числа гексаначчи:

0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, … (последовательность A001592 в OEIS )

Константа гексаначчи — это отношение, к которому стремятся соседние числа гексаначчи. Это корень многочлена , приблизительно 1,98358284342 (последовательность A118427 в OEIS ), а также удовлетворяет уравнению . ${\displaystyle x^{6}-x^{5}-x^{4}-x^{3}-x^{2}-x-1=0}$ ${\displaystyle x+x^{-6}=2}$

Числа Гептаначчи:

0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … (последовательность A122189 в OEIS )

Константа гептаначчи — это отношение, к которому стремятся соседние числа гептаначчи. Это корень многочлена , приблизительно 1,99196419660 (последовательность A118428 в OEIS ), а также удовлетворяет уравнению . ${\displaystyle x^{7}-x^{6}-x^{5}-x^{4}-x^{3}-x^{2}-x-1=0}$ ${\displaystyle x+x^{-7}=2}$

Числа Октаначчи:

0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ... (последовательность A079262 в 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, ... (последовательность A104144 в OEIS )

Предел отношения последовательных членов ряда -наччи стремится к корню уравнения ( OEIS : A103814 , OEIS : A118427 , OEIS : A118428 ). ${\displaystyle n}$ ${\displaystyle x+x^{-n}=2}$

Альтернативная рекурсивная формула для предела отношения двух последовательных чисел -наччи может быть выражена как ${\displaystyle r}$ ${\displaystyle n}$

${\displaystyle r=\sum _{k=0}^{n-1}r^{-k}}$.

Особым случаем является традиционный ряд Фибоначчи, дающий золотое сечение . ${\displaystyle n=2}$ ${\displaystyle \varphi =1+{\frac {1}{\varphi }}}$

Вышеуказанные формулы для отношения справедливы даже для рядов -nacci, сгенерированных из произвольных чисел. Предел этого отношения равен 2 по мере увеличения. Последовательность "infinacci", если бы ее можно было описать, после бесконечного числа нулей дала бы последовательность ${\displaystyle n}$ ${\displaystyle n}$

[..., 0, 0, 1,] 1, 2, 4, 8, 16, 32, …

которые являются просто степенями двойки .

Предел отношения для любого есть положительный корень характеристического уравнения ^[11] ${\displaystyle n>0}$ ${\displaystyle r}$

${\displaystyle x^{n}-\sum _{i=0}^{n-1}x^{i}=0.}$

Корень находится в интервале . Отрицательный корень характеристического уравнения находится в интервале (−1, 0), когда четно. Этот корень и каждый комплексный корень характеристического уравнения имеют модуль . ^[11] ${\displaystyle r}$ ${\displaystyle 2(1-2^{-n})<r<2}$ ${\displaystyle n}$ ${\displaystyle 3^{-n}<|r|<1}$

Ряд для положительного корня для любого имеет вид ^[11] ${\displaystyle r}$ ${\displaystyle n>0}$

${\displaystyle 2-2\sum _{i>0}{\frac {1}{i}}{\binom {(n+1)i-2}{i-1}}{\frac {1}{2^{(n+1)i}}}.}$

Не существует решения характеристического уравнения в терминах радикалов, когда 5 ≤ n ≤ 11. ^[11 ]

Элемент k последовательности n -наччи определяется как

${\displaystyle F_{k}^{(n)}=\left\lfloor {\frac {r^{k-1}(r-1)}{(n+1)r-2n}}\right\rceil \!,}$

где обозначает ближайшую целочисленную функцию, а — константа -наччи, которая является корнем ближайшего к 2 числа. ${\displaystyle \lfloor \cdot \rceil }$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle x+x^{-n}=2}$

Проблема подбрасывания монеты связана с последовательностью -nacci. Вероятность того, что ни одна последовательная решка не выпадет при подбрасывании идеализированной монеты, равна . ^[12] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle {\frac {1}{2^{m}}}F_{m+2}^{(n)}}$

Слово Фибоначчи

По аналогии со своим числовым аналогом, слово Фибоначчи определяется следующим образом:

${\displaystyle F_{n}:=F(n):={\begin{cases}{\text{b}}&n=0;\\{\text{a}}&n=1;\\F(n-1)+F(n-2)&n>1.\\\end{cases}}}$

где обозначает конкатенацию двух строк. Последовательность строк Фибоначчи начинается: ${\displaystyle +}$

б, а, аб, аба, абааб, абаабаба, абаабабаабааб, … (последовательность A106750 в OEIS )

Длина каждой строки Фибоначчи является числом Фибоначчи, и аналогично для каждого числа Фибоначчи существует соответствующая строка Фибоначчи.

Строки Фибоначчи появляются в качестве входных данных для наихудшего случая в некоторых компьютерных алгоритмах .

Если «a» и «b» представляют два разных материала или длины атомных связей, то структура, соответствующая строке Фибоначчи, представляет собой квазикристалл Фибоначчи , апериодическую квазикристаллическую структуру с необычными спектральными свойствами.

Свернутые последовательности Фибоначчи

Свернутая последовательность Фибоначчи получается применением операции свертки к последовательности Фибоначчи один или несколько раз. В частности, определите ^[13]

${\displaystyle F_{n}^{(0)}=F_{n}}$

и

${\displaystyle F_{n}^{(r+1)}=\sum _{i=0}^{n}F_{i}F_{n-i}^{(r)}}$

Первые несколько последовательностей:

${\displaystyle r=1}$: 0, 0, 1, 2, 5, 10, 20, 38, 71, … (последовательность A001629 в OEIS ).

${\displaystyle r=2}$: 0, 0, 0, 1, 3, 9, 22, 51, 111, … (последовательность A001628 в OEIS ).

${\displaystyle r=3}$: 0, 0, 0, 0, 1, 4, 14, 40, 105, … (последовательность A001872 в OEIS ).

Последовательности можно рассчитать с помощью рекуррентности

${\displaystyle F_{n+1}^{(r+1)}=F_{n}^{(r+1)}+F_{n-1}^{(r+1)}+F_{n}^{(r)}}$

Производящая функция th - й свертки равна ${\displaystyle r}$

${\displaystyle s^{(r)}(x)=\sum _{k=0}^{\infty }F_{n}^{(r)}x^{n}=\left({\frac {x}{1-x-x^{2}}}\right)^{r}.}$

Последовательности связаны с последовательностью полиномов Фибоначчи соотношением

${\displaystyle F_{n}^{(r)}=r!F_{n}^{(r)}(1)}$

где - производная th от . Эквивалентно, - коэффициент при разложении по степеням . ${\displaystyle F_{n}^{(r)}(x)}$ ${\displaystyle r}$ ${\displaystyle F_{n}(x)}$ ${\displaystyle F_{n}^{(r)}}$ ${\displaystyle (x-1)^{r}}$ ${\displaystyle F_{x}(x)}$ ${\displaystyle (x-1)}$

Первую свертку можно записать в терминах чисел Фибоначчи и Люка как ${\displaystyle F_{n}^{(1)}}$

${\displaystyle F_{n}^{(1)}={\frac {nL_{n}-F_{n}}{5}}}$

и следует за повторением

${\displaystyle F_{n+1}^{(1)}=2F_{n}^{(1)}+F_{n-1}^{(1)}-2F_{n-2}^{(1)}-F_{n-3}^{(1)}.}$

Аналогичные выражения можно найти для с возрастающей сложностью по мере увеличения. Числа являются суммами строк треугольника Хосои . ${\displaystyle r>1}$ ${\displaystyle r}$ ${\displaystyle F_{n}^{(1)}}$

Как и в случае с числами Фибоначчи, существует несколько комбинаторных интерпретаций этих последовательностей. Например, это число способов, которыми можно записать в виде упорядоченной суммы, включающей только 0, 1 и 2, где 0 используется ровно один раз. В частности, и 2 можно записать как 0 + 1 + 1 , 0 + 2 , 1 + 0 + 1 , 1 + 1 + 0 , 2 + 0 . ^[14] ${\displaystyle F_{n}^{(1)}}$ ${\displaystyle n-2}$ ${\displaystyle F_{4}^{(1)}=5}$

Другие обобщения

Полиномы Фибоначчи являются еще одним обобщением чисел Фибоначчи.

Последовательность Падована генерируется с помощью рекуррентности . ${\displaystyle P(n)=P(n-2)+P(n-3)}$

Последовательность коров Нараяны генерируется с помощью рекуррентности . ${\displaystyle N(k)=N(k-1)+N(k-3)}$

Случайную последовательность Фибоначчи можно определить, подбрасывая монету для каждой позиции последовательности и принимая во внимание, выпадает ли орел или решка. Работа Фюрстенберга и Кестена гарантирует, что эта последовательность почти наверняка растет экспоненциально с постоянной скоростью: константа не зависит от подбрасываний монеты и была вычислена в 1999 году Дивакаром Вишванатом. Теперь она известна как константа Вишваната . ${\displaystyle n}$ ${\displaystyle F(n)=F(n-1)+F(n-2)}$ ${\displaystyle F(n)=F(n-1)-F(n-2)}$

Repfigit , или число Кейта , — это целое число, такое что, когда его цифры начинают последовательность Фибоначчи с этим количеством цифр, в конечном итоге достигается исходное число. Примером является 47, потому что последовательность Фибоначчи, начинающаяся с 4 и 7 (4, 7, 11, 18, 29, 47), достигает 47. Repfigit может быть последовательностью трибоначчи, если в числе 3 цифры, числом тетраначчи, если число имеет четыре цифры, и т. д. Первые несколько repfigit:

14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, … (последовательность A007629 в OEIS )

Поскольку множество последовательностей, удовлетворяющих отношению, замкнуто относительно почленного сложения и почленного умножения на константу, его можно рассматривать как векторное пространство . Любая такая последовательность однозначно определяется выбором двух элементов, поэтому векторное пространство является двумерным . Если мы сократим такую ​​последовательность как , то последовательность Фибоначчи и сдвинутая последовательность Фибоначчи , как видно, образуют каноническую основу для этого пространства, что приводит к тождеству: ${\displaystyle S(n)=S(n-1)+S(n-2)}$ ${\displaystyle (S(0),S(1))}$ ${\displaystyle F(n)=(0,1)}$ ${\displaystyle F(n-1)=(1,0)}$

${\displaystyle S(n)=S(0)F(n-1)+S(1)F(n)}$

для всех таких последовательностей S. Например, если S — это последовательность Лукаса 2, 1, 3, 4, 7, 11, ... , то мы получаем

${\displaystyle L(n)=2F(n-1)+F(n)}$.

Н-сгенерированная последовательность Фибоначчи

Мы можем определить N -генерированную последовательность Фибоначчи (где N — положительное рациональное число ): если

${\displaystyle N=2^{a_{1}}\cdot 3^{a_{2}}\cdot 5^{a_{3}}\cdot 7^{a_{4}}\cdot 11^{a_{5}}\cdot 13^{a_{6}}\cdot \ldots \cdot p_{r}^{a_{r}},}$

где p _r — r -е простое число, тогда мы определяем

${\displaystyle F_{N}(n)=a_{1}F_{N}(n-1)+a_{2}F_{N}(n-2)+a_{3}F_{N}(n-3)+a_{4}F_{N}(n-4)+a_{5}F_{N}(n-5)+...}$

Если , то , и если , то . ^{[ необходима цитата ]} ${\displaystyle n=r-1}$ ${\displaystyle F_{N}(n)=1}$ ${\displaystyle n<r-1}$ ${\displaystyle F_{N}(n)=0}$

Полупоследовательность Фибоначчи

Полупоследовательность Фибоначчи (последовательность A030067 в OEIS ) определяется с помощью той же рекурсии для нечетно-индексированных членов и , но для четных индексов , . Бисекция A030068 нечетно-индексированных членов, таким образом, проверяет и строго возрастает . Это дает набор получисел Фибоначчи ${\displaystyle a(2n+1)=a(2n)+a(2n-1)}$ ${\displaystyle a(1)=1}$ ${\displaystyle a(2n)=a(n)}$ ${\displaystyle n\geq 1}$ ${\displaystyle s(n)=a(2n-1)}$ ${\displaystyle s(n+1)=s(n)+a(n)}$

1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, 53, 69, 70, 87, 93, 116, 119, 145, 154, ... (последовательность A030068 в OEIS )

которые происходят как ${\displaystyle s(n)=a(2^{k}(2n-1)),k=0,1,...\,.}$

Ссылки

1. Триана, Хуан. Числа Негафибоначчи через матрицы. Вестник ТИКМИ, 2019, стр. 19–24.
2. "Что такое число Фибоначчи? -- от Гарри Дж. Смита". 2009-10-27. Архивировано из оригинала 27 октября 2009 года . Получено 2022-04-12 .
3. Правин Чандра и Эрик В. Вайсштейн . «Число Фибоначчи». MathWorld .
4. Моррисон, DR (1980), «Массив Столярского пар Вайтхоффа», Сборник рукописей, связанных с последовательностью Фибоначчи (PDF) , Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 134–136, архивировано из оригинала (PDF) 2016-03-04 , извлечено 2012-07-15.
5. Гарднер, Мартин (1961). The Scientific American Book of Mathematical Puzzles and Diversions, Vol. II . Саймон и Шустер. стр. 101.
6. Туэнтер, Ханс Дж. Х. (октябрь 2023 г.). «В поисках товарища Агронома: немного истории Трибоначчи». Американский математический ежемесячник . 130 (8): 708–719. дои : 10.1080/00029890.2023.2231796. МР  4645497.
7. Агрономоф, М. (1914). «Sur une suite recurrente». Матезис . 4 : 125–126.
8. Подани, Янош; Кун, Адам; Силадьи, Андраш (2018). «Как быстро растет популяция слонов по Дарвину?» (PDF) . Журнал истории биологии . 51 (2): 259–281. дои : 10.1007/s10739-017-9488-5. PMID  28726021. S2CID  3988121.
9. Файнберг, М. (1963). «Фибоначчи-Трибоначчи». Ежеквартальный журнал Фибоначчи . 1 : 71–74.
10. Саймон Плуфф, 1993
11. Вольфрам, DA (1998). "Решение обобщенных повторений Фибоначчи" (PDF) . Fib. Quart .
12. Эрик В. Вайсштейн . «Подбрасывание монеты». MathWorld .
13. VE Hoggatt, Jr. и M. Bicknell-Johnson, «Свёрточные последовательности Фибоначчи», Fib. Quart. , 15 (1977), стр. 117-122.
14. Sloane, N. J. A. (ред.). "Последовательность A001629". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.

Внешние ссылки

• «Число Трибоначчи», Энциклопедия математики , EMS Press , 2001 [1994]