Обобщённые числа Фибоначчи (KQkQp~uudy cnvlg SnQkugccn)

Числа Фибоначчи образуют определённую с помощью рекурсии последовательность

$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)^{n+1}F_{n}$.

См. также Негафибоначчиевы числа.

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

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

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

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

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

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

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

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

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

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

для которой выполняется $\operatorname {Fib} (n)=F_{n}$ для всех целых чисел n.

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

$\operatorname {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 может быть взята любая абелева группа (рассматриваемая как Z-модуль). Тогда последовательности Фибоначчи образуют 2-мерный Z-модуль.

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

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

2-мерный Z-модуль последовательностей целых чисел Фибоначчи состоит из всех целых последовательностей, удовлетворяющих соотношению $g(n+2)=g(n)+g(n+1)$. Если выразить в терминах двух первых начальных значений, получим

$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}}},$

где φ — золотое сечение.

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

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

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

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

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

Мы имеем $L_{1}=1$ и $L_{2}=3$. Выполняется:

${\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}}$

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

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

Последовательности Люка

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

$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, … последовательность 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-последовательности Фибоначчи. Она называется также n-м отношением ценного металла и является единственным положительным корнем уравнения $x^{2}-nx-1=0$. Например, в случае $n=1$ константа равна ${\tfrac {1+{\sqrt {5}}}{2}}$, или золотому сечению, а в случае $n=2$ константа равна 1 + √2, или серебряному сечению. Для общего случая n-константа равна ${\tfrac {n+{\sqrt {n^{2}+4}}}{2}}$.

В общем случае $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, … последовательность 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 — это последовательность целых чисел, в которой каждый элемент является суммой предыдущих n элементов (за исключением первых n элементов последовательности). Обычные числа Фибоначчи имеют порядок 2. Случаи $n=3$ и $n=4$ тщательно исследованы. Число разложений неотрицательных целых чисел на части, не превосходящие n, является последовательностью Фибоначчи порядка n. Последователь количеств строк из 0 и 1 длины m, содержащих не более n последовательных нулей, также является последовательностью Фибоначчи порядка n.

Эти последовательности, их границы отношений членов и их пределы отношений членов исследовал Марк Барр в 1913.

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

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

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

Постоянная трибоначчи

${\frac {1+{\sqrt[{3}]{19+3{\sqrt {33}}}}+{\sqrt[{3}]{19-3{\sqrt {33}}}}}{3}}\approx 1,839286755214161,$ последовательность A058265 в OEIS

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

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

$\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.$

Числа трибоначчи задаются также формулой

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

где ⌊ • ⌉ означает ближайшее целое и

${\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)

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

Константа тетраначчи выражается в терминах радикалов

$\left(p_{1}+{\tfrac {1}{4}}\right)+{\sqrt {\left(p_{1}+{\tfrac {1}{4}}\right)^{2}-{\frac {2\lambda _{1}}{p_{1}}}\left(p_{1}+{\tfrac {1}{4}}\right)+{\frac {7}{24p_{1}}}+{\tfrac {1}{6}}}}$

где

${\begin{aligned}p_{1}&={\sqrt {\lambda _{1}+{\tfrac {11}{48}}}}\\\lambda _{1}&={\frac {{\sqrt[{3}]{3{\sqrt {1689}}-65}}-{\sqrt[{3}]{3{\sqrt {1689}}+65}}}{12{\sqrt[{3}]{2}}}}.\end{aligned}}$

Более высокие порядки

Были вычислены числа пентаначчи (5 порядка), гексаначчи (6 порядка) и гептаначчи (7 порядка).

Числа пентаначчи (5 порядка):

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

Числа гексаначчи (6 порядка):

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

Числа гептаначчи (7 порядка):

0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, … последовательность A122189 в 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, … последовательность A079262 в 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, … последовательность A104144 в OEIS

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

Альтернативная рекурсивная формула предела отношения r двух последовательных чисел n-наччи

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

Частный случай $n=2$ является традиционной последовательностью Фибоначчи и даёт золотое сечение $\varphi =1+{\tfrac {1}{\varphi }}$.

Вышеприведённые формулы для отношения выполняются для последовательностей n-наччи, сгенерированных из произвольных чисел. Предел этого отношения равен 2 при n, стремящемся к бесконечности. Последовательность чисел «бесконечно-наччи», если её попытаться описать, должна начинаться с бесконечного числа нулей, после чего должна идти последовательность

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

то есть просто степени двойки.

Предел последовательности для любого $n>0$ является положительным корнем r характеристического уравнения

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

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

Последовательность для положительного корня r для любого $n>0$

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

Не существует решения характеристического уравнения в терминах радикалов, если $5\leqslant n\leqslant 11$.

k-й элемент последовательности n-наччи задаётся формулой

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

где ⌊ • ⌉ означает ближайшее целое, а r — константа n-наччи, которая является корнем $x+x^{-n}=2$, ближайшим к 2.

Задача подбрасования монеты связана с последовательностью n-наччи. Вероятность, что не выпадет n раз последовательно решка в m бросаниях идеальной монеты, равна ${\tfrac {1}{2^{m}}}F_{m+2}^{(n)}$.

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

Основная статья: Слово Фибоначчи

По аналогии числовому аналогу слово Фибоначчи определяется как

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

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

b, a, ab, aba, abaab, abaababa, abaababaabaab, … последовательность A106750 в OEIS

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

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

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

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

Свёрнутая последовательность Фибоначчи получается путём применения операции свёртки к последовательности Фибоначчи один и более раз. Определим:

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

и

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

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

r = 1: 0, 0, 1, 2, 5, 10, 20, 38, 71, … A001629.

r = 2: 0, 0, 0, 1, 3, 9, 22, 51, 111, … A001628.

r = 3: 0, 0, 0, 0, 1, 4, 14, 40, 105, … A001872.

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

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

Производящая функция r-ой свёртки равна

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

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

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

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

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

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

и удовлетворяет рекуррентному соотношению

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

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

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

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

Многочлены Фибоначчи являются другим обобщением чисел Фибоначчи.

Последовательность Падована образована рекуррентным соотношением $P(n)=P(n-2)+P(n-3)$.

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

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

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

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

$S(n)=S(0)F(n-1)+S(1)F(n)$

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

$L(n)=2F(n-1)+F(n)$.

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

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

Если

$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 ...\cdot P_{r}^{a_{r}},$

где P_r — это r-ое простое число, мы определяем

$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)+...$

Если $n=r-1$, полагаем $F_{N}(n)=1$, а в случае $n<r-1$, полагаем $F_{N}(n)=0$.

Последовательность	N	Последовательность OEIS
Последовательность Фибоначчи	6	A000045
Последовательность Пелля	12	A000129
Последовательность Якобсталя	18	A001045
Последовательность трибоначчи	30	A000073
Последовательность тетраначчи	210	A000288
Последовательность Падована	15	A000931

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

Полуфиббоначиева последовательность (A030067) определяется посредством той же рекуррентной формулы для членов с нечётными индексами $a(2n+1)=a(2n)+a(2n-1)$ и $a(1)=1$, но для чётных индексов берётся $a(2n)=a(n)$, $n\geqslant 1$. Выделенные нечётные члены (A030068) $s(n)=a(2n-1)$ удовлетворяют уравнению $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,

для которых верна формула $s(n)=a(2^{k}(2n-1)),k=0,1,...$.

Ссылки

• Hazewinkel, Michiel, ed. (2001), "Tribonacci number", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4