Чи́сла Фибона́ччи (вариант написания — Фибона́чи ) — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность в OEIS ),

в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел . Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи ) .

Правда, в некоторых книгах, особенно в старых ^{[ каких? ]} , член ${\displaystyle F_{0}}$ , равный нулю, опускается — тогда последовательность Фибоначчи начинается с ${\displaystyle F_{1}=F_{2}=1}$ .

Говоря более формально, последовательность чисел Фибоначчи ${\displaystyle \{F_{n}\}}$ задаётся линейным рекуррентным соотношением :

${\displaystyle F_{0}=0,\quad F_{1}=1,\quad F_{n}=F_{n-1}+F_{n-2}}$ ,

где ${\displaystyle \ n\geqslant 2,\ n\in \mathbb {Z} }$ .

Иногда числа Фибоначчи рассматривают и для отрицательных значений ${\displaystyle n}$ как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. Соответственно, члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: ${\displaystyle F_{n}=F_{n+2}-F_{n+1}}$ :

n	…	−10	−9	−8	−7	−6	−5	−4	−3	−2	−1	0	1	2	3	4	5	6	7	8	9	10	…
${\displaystyle F_{n}}$	…	−55	34	−21	13	−8	5	−3	2	−1	1	0	1	1	2	3	5	8	13	21	34	55	…

Легко заметить, что ${\displaystyle F_{-n}=(-1)^{n+1}F_{n}}$ .

Происхождение

Последовательность Фибоначчи была хорошо известна в древней Индии , где она применялась в метрических науках ( просодии , другими словами — стихосложении) намного раньше, чем стала известна в Европе .

Образец длиной n может быть построен путём добавления S к образцу длиной n − 1 , либо L к образцу длиной n − 2 — и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности . Дональд Кнут рассматривает этот эффект в книге « Искусство программирования ».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи , в его труде « Книга абака » (1202) . Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают , — а в качестве искомого выдвигает количество пар кроликов через год.

• В начале первого месяца есть только одна новорождённая пара (1) .
• В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1).
• В конце второго месяца первая пара рождает новую пару и опять спаривается (2).
• В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
• В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).

В конце ${\displaystyle n}$ -го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количеству новорождённых пар, которых будет столько же, сколько пар было два месяца назад, то есть ${\displaystyle F_{n}=F_{n-2}+F_{n-1}}$ . Возможно, эта задача также оказалась первой, моделирующей экспоненциальный рост популяции .

Название «последовательность Фибоначчи» впервые было использовано теоретиком XIX века Эдуардом Люка .

Формула Бине

Формула Бине выражает в явном виде значение ${\displaystyle F_{n}}$ как функцию от n :

${\displaystyle F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\varphi -(-\varphi )^{-1}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}},}$

где ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ — золотое сечение и ${\displaystyle \varphi }$ и ${\displaystyle (-\varphi )^{-1}=1-\varphi }$ являются корнями характеристического уравнения ${\displaystyle x^{2}-x-1=0.}$ Вообще, аналогичная формула существует для любой линейной рекуррентной последовательности , какой служит и последовательность Фибоначчи.

Обоснование

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

${\displaystyle {\begin{aligned}x^{4}&=2x^{2}+x=2(x+1)+x=\\&=3x+2,\\x^{5}&=3x^{2}+2x=3(x+1)+2x=\\&=5x+3,\\x^{6}&=5x^{2}+3x=5(x+1)+3x=\\&=8x+5,\\x^{7}&=8x^{2}+5x=8(x+1)+5x=\\&=13x+8,\\&\cdots \end{aligned}}}$

Таким образом образуется общее уравнение: ${\displaystyle x^{n}=F_{n}x+F_{n-1}.}$ Чтобы это уравнение обратить в верное равенство и отсюда выразить сами числа Фибоначчи, нужно подставить корни ${\displaystyle \varphi }$ и ${\displaystyle -\varphi ^{-1}\colon }$

${\displaystyle {\begin{cases}\varphi ^{n}=F_{n}\varphi +F_{n-1},\\(-\varphi )^{-n}=-F_{n}\varphi ^{-1}+F_{n-1},\end{cases}}}$

${\displaystyle \varphi ^{n}-(-\varphi )^{-n}=F_{n}[\varphi -(-\varphi )^{-1}],\qquad \varphi ^{n}+(-\varphi )^{-n}\cdot \varphi ^{2}=F_{n-1}(1+\varphi ^{2}),}$

${\displaystyle \color {Black}{\tfrac {1}{\sqrt {5}}}\left(({\tfrac {1+{\sqrt {5}}}{2}})^{n}-({\tfrac {1-{\sqrt {5}}}{2}})^{n}\right)=F_{n},\qquad {\tfrac {1}{\sqrt {5}}}\left(({\tfrac {1+{\sqrt {5}}}{2}})^{n-1}-({\tfrac {1-{\sqrt {5}}}{2}})^{n-1}\right)=F_{n-1}.}$

Следствие и обобщение

Из формулы Бине следует, что для всех ${\displaystyle n\geqslant 0}$ число ${\displaystyle F_{n}}$ есть округление ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}},}$ то есть ${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil .}$ В частности, при ${\displaystyle n\to \infty }$ справедлива асимптотика ${\displaystyle F_{n}\sim {\frac {\varphi ^{n}}{\sqrt {5}}}.}$

Формула Бине может быть аналитически продолжена следующим образом:

${\displaystyle F_{z}={\frac {1}{\sqrt {5}}}\left(\varphi ^{z}-{\frac {\cos {\pi z}}{\varphi ^{z}}}\right).}$

При этом соотношение ${\displaystyle F_{z+2}=F_{z+1}+F_{z}}$ выполняется для любого комплексного числа z .

Тождества

• ${\displaystyle F_{1}+F_{2}+F_{3}+\dots +F_{n}=F_{n+2}-1.}$

• ${\displaystyle F_{1}+F_{3}+F_{5}+\dots +F_{2n-1}=F_{2n}.}$

• ${\displaystyle F_{2}+F_{4}+F_{6}+\dots +F_{2n}=F_{2n+1}-1.}$

Это тождество можно доказать вычитанием первого из второго: ${\displaystyle {\begin{alignedat}{2}(F_{1}+F_{2}+\dots +F_{{\color {Red}2}n})-(F_{1}+F_{3}+\dots +F_{2n-1})&=F_{{\color {Red}2}n+2}-1-F_{2n},\\F_{2}+F_{4}+\dots +F_{2n}&=F_{2n+1}-1.\\\end{alignedat}}}$

• ${\displaystyle F_{n+1}F_{n+2}-F_{n}F_{n+3}=(-1)^{n}.}$
• ${\displaystyle F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+\dots +F_{n}^{2}=F_{n}F_{n+1}}$ (см. рис.).
• ${\displaystyle F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}.}$
• ${\displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}.}$
• ${\displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}-F_{n-1}^{3}.}$
• ${\displaystyle F_{5n}=25F_{n}^{5}+25(-1)^{n}F_{n}^{3}+5F_{n}.}$
• ${\displaystyle F_{n+1}=C_{n}^{0}+C_{n-1}^{1}+C_{n-2}^{2}+\dots }$ , где ${\displaystyle C_{n}^{k}}$ — биномиальные коэффициенты .

И более общие формулы:

• ${\displaystyle F_{n+m}=F_{n-1}F_{m}+F_{n}F_{m+1}=F_{n+1}F_{m+1}-F_{n-1}F_{m-1}.}$
• ${\displaystyle F_{(k+1)n}=F_{n-1}F_{kn}+F_{n}F_{kn+1}.}$
• ${\displaystyle F_{n}=F_{l}F_{n-l+1}+F_{l-1}F_{n-l}.}$
• Числа Фибоначчи представляются значениями континуант на наборе единиц: ${\displaystyle F_{n+1}=K_{n}(1,\dots ,1),}$ то есть

  ${\displaystyle F_{n+1}=\det {\begin{pmatrix}1&1&0&\cdots &0\\-1&1&1&\ddots &\vdots \\0&-1&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &1\\0&\cdots &0&-1&1\end{pmatrix}}}$ , а также ${\displaystyle \ F_{n+1}=\det {\begin{pmatrix}1&i&0&\cdots &0\\i&1&i&\ddots &\vdots \\0&i&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &i\\0&\cdots &0&i&1\end{pmatrix}},}$

где матрицы имеют размер ${\displaystyle n\times n}$ и где i — мнимая единица .

• Числа Фибоначчи можно выразить через многочлены Чебышёва :

  ${\displaystyle F_{n+1}=(-i)^{n}U_{n}\left({\frac {-i}{2}}\right),}$

  ${\displaystyle F_{2n+2}=U_{n}\left({\frac {3}{2}}\right).}$

• Для любого n справедливо

  ${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}$

• Как следствие, подсчёт определителей даёт тождество Кассини :

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

• С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана : ${\displaystyle F_{n}^{2}-F_{n-r}F_{n+r}=(-1)^{n-r}F_{r}^{2}.}$

• ${\displaystyle F_{n+1}={\frac {F_{n}+{\sqrt {5F_{n}^{2}+4(-1)^{n}}}}{2}}.}$
  Это утверждение выводится из тождества Кассини при помощи основного соотношения чисел Фибоначчи: ${\displaystyle (-1)^{n}=F_{n+1}(F_{n+1}-F_{n})-F_{n}^{2}}$ ${\displaystyle \Longleftrightarrow }$ ${\displaystyle 0={\color {Red}F_{n+1}}^{2}-{\color {Red}F_{n+1}}F_{n}-(F_{n}^{2}+(-1)^{n}).}$

Свойства

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть ${\displaystyle (F_{m},F_{n})=F_{(m,n)}.}$ Следствия:
  • ${\displaystyle F_{m}}$ делится на ${\displaystyle F_{n}}$ тогда и только тогда, когда ${\displaystyle m}$ делится на ${\displaystyle n}$ (за исключением ${\displaystyle n=2}$ ). В частности, ${\displaystyle F_{m}}$ делится на ${\displaystyle F_{3}=2}$ (то есть является чётным) только для ${\displaystyle m=3k;}$ ${\displaystyle F_{m}}$ делится на ${\displaystyle F_{4}=3}$ только для ${\displaystyle m=4k;}$ ${\displaystyle F_{m}}$ делится на ${\displaystyle F_{5}=5}$ только для ${\displaystyle m=5k}$ и т. д.
  • ${\displaystyle F_{m}}$ может быть простым только для простых ${\displaystyle m}$ (с единственным исключением ${\displaystyle m=4}$ ). Например, число ${\displaystyle F_{13}=233}$ простое, и его индекс 13 также прост. Но, даже если число ${\displaystyle m}$ простое, число ${\displaystyle F_{m}}$ не всегда оказывается простым, и наименьший контрпример — ${\displaystyle F_{19}=4181=37\cdot 113.}$ Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
• Последовательность чисел Фибоначчи является частным случаем возвратной последовательности , её характеристический многочлен ${\displaystyle x^{2}-x-1}$ имеет корни ${\displaystyle \varphi }$ и ${\displaystyle -{\frac {1}{\varphi }}.}$
• Отношения ${\displaystyle {\frac {F_{n+1}}{F_{n}}}}$ являются подходящими дробями золотого сечения ${\displaystyle \phi \colon }$ в частности, ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$
• Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы

  ${\displaystyle F_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }{n-k \choose k}.}$

• Нахождение числа Фибоначчи ${\displaystyle F_{n}}$ с помощью Бинома Ньютона ${\displaystyle F_{n}={1 \over 2^{n-1}}\sum _{k=0}^{\lfloor n/2\rfloor }{n \choose 2k+1}5^{k}}$

• В 1964 году Дж. Кон ( J. H. E. Cohn ) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:

  ${\displaystyle F_{0}=0^{2}=0,}$ ${\displaystyle F_{1}=1^{2}=1,}$ ${\displaystyle F_{2}=1^{2}=1,}$ ${\displaystyle F_{12}=12^{2}=144.}$

• Производящей функцией последовательности чисел Фибоначчи является:

  ${\displaystyle x+x^{2}+2x^{3}+3x^{4}+5x^{5}+\dots =\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}}$

  • В частности, 1/998,999 = 0 .00 1 00 1 00 2 00 3 00 5 00 8 0 13 0 21 …
• Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена

  ${\displaystyle z(x,y)=2xy^{4}+x^{2}y^{3}-2x^{3}y^{2}-y^{5}-x^{4}y+2y}$

на множестве неотрицательных целых чисел x и y .

• Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
• Период чисел Фибоначчи по модулю натурального числа ${\displaystyle n}$ называется периодом Пизано и обозначается ${\displaystyle \pi (n)}$ . Периоды Пизано ${\displaystyle \pi (n)}$ образуют последовательность:

  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность в OEIS ).

  • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом ${\displaystyle \pi (10)=60}$ , последняя пара цифр чисел Фибоначчи образует последовательность с периодом ${\displaystyle \pi (100)=300}$ , последние три цифры — с периодом ${\displaystyle \pi (1000)=1500,}$ последние четыре — с периодом ${\displaystyle \pi (10000)=15000,}$ последние пять — с периодом ${\displaystyle \pi (100000)=150000}$ и т. д.
• Натуральное число ${\displaystyle N}$ является числом Фибоначчи тогда и только тогда, когда ${\displaystyle 5N^{2}+4}$ или ${\displaystyle 5N^{2}-4}$ является квадратом .
• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи .
• Число Фибоначчи ${\displaystyle F_{n+2}=F_{n+1}+F_{n}}$ равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом ${\displaystyle F_{n+1}}$ равно количеству таких кортежей, начинающихся с нуля, а ${\displaystyle F_{n}}$ — начинающихся с единицы.
• Произведение любых ${\displaystyle n}$ подряд идущих чисел Фибоначчи делится на произведение первых ${\displaystyle n}$ чисел Фибоначчи.
• Бесконечная сумма чисел, обратных числам Фибоначчи, сходится, его сумма (« обратная постоянная Фибоначчи ») равна 3,359884...

Вариации и обобщения

• Числа трибоначчи
• Числа Фибоначчи являются частным случаем последовательностей Люка ${\displaystyle F_{n}=U_{n}(1,-1)}$ .
  • При этом их дополнением являются числа Люка ${\displaystyle L_{n}=V_{n}(1,-1)}$ .

В других областях

Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространённый миф, который часто оказывается неточной подгонкой под желаемый результат .

В природе

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

В искусстве

В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Ш. Руставели « Витязь в тигровой шкуре » и на картинах художников .

Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке

В кодировании

В теории кодирования предложены устойчивые так называемые « коды Фибоначчи » , причём основание этих кодов — иррациональное число.

См. также

• Дерево Фибоначчи
• Метод Фибоначчи с запаздываниями
• Метод Фибоначчи поиска экстремума
• Фибоначчи
• Фибоначчиева система счисления
• Числа Леонардо
• Таблица Витхоффа
• Последовательность коров Нараяны
• Золотое сечение
• Пропорционирование
• Последовательность без простых чисел

Примечания

Литература

• Н. Н. Воробьёв . . — Наука, 1978. — Т. 39. — ( Популярные лекции по математике ).
• А. И. Маркушевич . . — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — ( Популярные лекции по математике ).
• А. Н. Рудаков. // Математическое Просвещение , третья серия. — 2000. — Т. 4 .
• Дональд Кнут . Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М. : , 2006. — С. 720. — ISBN 0-201-89683-4 .
• Дональд Кнут , Роналд Грэхем , Орен Паташник . Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М. : Мир ; , 2006. — С. 703. — ISBN 5-94774-560-7 .
• Грант Аракелян . Математика и история золотого сечения. — М.: Логос, 2014. — 404 с. — ISBN 978-5-98704-663-0 .
• Ball, Keith M (2003), "8: Fibonacci's Rabbits Revisited", Strange Curves, Counting Rabbits, and Other Mathematical Explorations , Princeton, NJ: Princeton University Press , ISBN 978-0-691-11321-0 .
• Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics , New York: Springer, ISBN 978-1-4419-7022-0 .
• [in английский] (2011), A Walk Through Combinatorics (3rd ed.), New Jersey: World Scientific, ISBN 978-981-4335-23-2 .
  • Bóna, Miklós (2016), A Walk Through Combinatorics (4th Revised ed.), New Jersey: World Scientific, ISBN 978-981-3148-84-0 .
• Lemmermeyer, Franz (2000), Reciprocity Laws: From Euler to Eisenstein , Springer Monographs in Mathematics, New York: Springer, ISBN 978-3-540-66957-9 .
• Livio, Mario . (англ.) . — First trade paperback. — New York City: (англ.) ( , 2003. — ISBN 0-7679-0816-3 .
• Lucas, Édouard (1891), (фр.) , vol. 1, Paris: Gauthier-Villars, .
• Pisano, Leonardo (2002), Fibonacci's Liber Abaci: A Translation into Modern English of the Book of Calculation , Sources and Studies in the History of Mathematics and Physical Sciences, Sigler, Laurence E, trans, Springer, ISBN 978-0-387-95419-6

Ссылки

• (англ.)
• (англ.)