Фибоначчи формула – Числа Фибоначчи: ищем секрет мироздания — Детская игровая комната «Волшебный лес»

Posted on 18.11.202026.12.2019 by alexxlab

Содержание

Лекция № 8. Числа фибоначчи и простые числа

Задача Фибоначчи

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

Нужно определить, сколько кроликов будет на ферме через n месяцев, если в начальный момент времени был только один новорожденный кролик.

Очевидно, что фермер имеет одного кролика в первый месяц и одного кролика – во второй месяц. На третий месяц будет уже два кролика, на четвертый – три и т.д. Обозначим количество кроликов в

n месяце как

. Таким образом,

, …

Можно построить алгоритм, позволяющий найти при любомn.

Согласно условию задачи общее количество кроликов вn+1 месяце раскладывается на три составляющие:

одномесячные кролики, не способные к размножению, в количестве

;

кролики, способные к размножению, в количестве ;
новорожденные кролики, их количество также равно .

Таким образом, получим

. (8.1)

Формула (8.1) позволяет вычислить ряд чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …

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

Если принять и , то с помощью формулы (8.1) можно определить все остальные числа Фибоначчи. Формула (8.1) называется рекуррентной формулой (recurrence – «возвращение» на латыни).

Пример 8.1. Предположим, что имеется лестница в n ступенек. Мы можем подниматься по ней с шагом в одну ступеньку, либо – с шагом в две ступеньки. Сколько существует комбинаций различных способов подъема?

Если n = 1, имеется только один вариант решения задачи. Для n = 2 существует 2 варианта: два единичных шага либо один двойной. Для n = 3 существует 3 варианта: три единичных шага, либо один единичный и один двойной, либо один двойной и один единичный.

В следующем случае

n = 4, имеем 5 возможностей (1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2).

Для того чтобы ответить на заданный вопрос при произвольном n, обозначим количество вариантов как , и попробуем определитьпо известными . Если мы стартуем с единичного шага, то имеем комбинаций для оставшихсяn ступенек. Если стартуем с двойного шага, то имеем комбинаций для оставшихсяn–1 ступенек. Общее количество вариантов для

n+1 ступенек равно

. (8.2)

Полученная формула как близнец напоминает формулу (8.1). Тем не менее, это не позволяет отождествлять количество комбинаций с числами Фибоначчи. Мы видим, например, что, но. Однако имеет место следующая зависимость:

Это справедливо для n = 1, 2, и также справедливо для каждого n. Числа Фибоначчи и количество комбинаций

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

у них различаются.

Пример 8.2. Этот пример имеет практическое значение для задач помехоустойчивого кодирования. Найдем число всех двоичных слов длины n, не содержащих несколько нулей подряд. Обозначим это число через . Очевидно,, а слова длины 2, удовлетворяющие нашему ограничению, таковы: 10, 01, 11, т.е.

. Пусть

– такое слово изn символов. Если символ

, то

может быть произвольным (

)-буквенным словом, не содержащим несколько нулей подряд. Значит, число слов с единицей на конце равно

Если же символ , то обязательно, а первые

символа

могут быть произвольными с учетом рассматриваемых ограничений. Следовательно, имеется

слов длины n с нулем на конце. Таким образом, общее число интересующих нас слов равно

С учетом того, что и, полученная последовательность чисел – это числа Фибоначчи.

Пример 8.3. В примере 7.6 мы нашли, что число двоичных слов постоянного веса t (и длиной k) равно

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

Рассуждать можно так. Пусть число нулей в рассматриваемых словах. В любом слове имеетсяпромежутков между ближайшими нулями, в каждом из которых находится одна или несколько единиц. Предполагается, что. В противном случае нет ни одного слова без рядом стоящих нулей.

Если из каждого промежутка удалить ровно по одной единице, то получим слово длины , содержащее

нулей. Любое такое слово может быть получено указанным образом из некоторого (и притом только одного)k-буквенного слова, содержащего

нулей, никакие два из которых не стоят рядом. Значит, искомое число совпадает с числом всех слов длины

, содержащих ровно

нулей, т.е. равно

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

обозначаетнаименьшее целое число, большее или равное

. Например, если

, то

; а если

, то

. По-английски эту операцию называютceil («потолок»). Также встречается символ

, который обозначаетнаибольшее целое число, меньшее или равное

. По-английски эту операцию называютfloor («пол»).

Если , то. Если, то. Если, то.

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

И оно действительно выполняется:

Здесь мы использовали полученную ранее формулу (4.4): .

Сумма чисел Фибоначчи

Определим сумму первых n чисел Фибоначчи.

0 = 0,

0+1 = 1,

0+1+1 = 2,

0+1+1+2 = 4,

0+1+1+2+3 = 7,

0+1+1+2+3+5 = 12,

0+1+1+2+3+5+8 = 20,

0+1+1+2+3+5+8+13 = 33.

Легко заметить, что прибавлением к правой части каждого уравнения единицы мы снова получаем число Фибоначчи. Общая формула для определения суммы первых n чисел Фибоначчи имеет вид:

Докажем это, используя метод математической индукции. Для этого запишем:

Эта сумма должна быть равна .

Сократив левую и правую часть уравнения на –1, получим уравнение (6.1).

Формула для чисел Фибоначчи

Теорема 8.1. Числа Фибоначчи можно рассчитать по формуле

Доказательство. Убедимся в справедливости этой формулы для n = 0, 1, а затем докажем справедливость данной формулы для произвольного n по индукции. Вычислим отношение двух ближайших чисел Фибоначчи:

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

преобразуется в

которое после упрощений выглядит так

Мы получили квадратное уравнение, корни которого равны:

Теперь можем записать:

(где c является константой). Оба члена и не дают чисел Фибоначчи, например , в то время как. Однако разность удовлетворяет рекуррентному уравнению:

Для n=0 эта разность дает, то есть: . Однако при n=1 мы имеем . Чтобы получить , необходимо принять:.

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

При возрастании n член становится очень большим, в то время как, и роль членав разности сокращается. Поэтому при больших n приближенно можем записать

Мы игнорируем 1/2 (поскольку числа Фибоначчи возрастают до бесконечности при росте n до бесконечности).

Отношение называется золотым сечением, его используют за пределами математики (например, в скульптуре и архитектуре). Золотым сечением является отношение между диагональю и стороной правильного пятиугольника (рис. 8.1).

Рис. 8.1. Правильный пятиугольник и его диагонали

Для обозначения золотого сечения принято использовать букву в честь известного афинского скульптора Фидия.

Простые числа

Все натуральные числа, большие единицы, распадаются на два класса. К первому относятся числа, имеющие ровно два натуральных делителя, единицу и самого себя, ко второму – все остальные. Числа первого класса называют простыми, а второго – составными. Простые числа в пределах первых трех десятков: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

Свойства простых чисел и их связь со всеми натуральными числами изучалась Евклидом (3 век до нашей эры). Если выписывать простые числа подряд, то можно заметить, что относительная плотность их убывает. На первый десяток их приходится 4, т. е. 40%, на сотню – 25, т.е. 25%, на тысячу – 168, т.е. меньше 17%, на миллион – 78498, т.е. меньше 8%, и т.д.. Тем не менее, их общее число бесконечно.

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

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

Изучение распределения простых чисел привело к созданию алгоритма, позволяющего получать таблицы простых чисел. Таким алгоритмом является решето Эратосфена (3 век до нашей эры). Этот метод заключается в отсеивании (например, путем зачеркивания) тех целых чисел заданной последовательности , которые делятся хотя бы на одно из простых чисел, меньших.

Теорема 8.2. (теорема Евклида). Число простых чисел бесконечно.

Доказательство. Теорему Евклида о бесконечности числа простых чисел докажем способом, предложенным Леонардом Эйлером (1707–1783). Эйлер рассмотрел произведение по всем простым числам p:

при . Это произведение сходится, и если его раскрыть, то в силу однозначности разложения натуральных чисел на простые сомножители получается, что оно равняется сумме ряда, откуда следует тождество Эйлера:

Так как при ряд справа расходится (гармонический ряд), то из тождества Эйлера следует теорема Евклида.

Русский математик П.Л. Чебышев (1821–1894) вывел формулу, определяющую пределы, в которых заключено число простых чисел , не превосходящихX:

где ,.

studfile.net

Последовательность Фибоначчи — это… Что такое Последовательность Фибоначчи?

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

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

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

Более формально, последовательность чисел Фибоначчи $\left\{F_n\right\}$ задается рекуррентным соотношением:

$F_1 = 1,\quad F_2 = 1,\quad F_{n+1} = F_n + F_{n-1} \quad n\in\mathbb{N}.$

Иногда числа Фибоначчи рассматривают и для неположительных номеров n как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад»: 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
F_n	−55	34	−21	13	−8	5	−3	2	−1	1	0	1	1	2	3	5	8	13	21	34	55

Легко видеть, что F _{− n} = ( − 1)^{n + 1}F_n. Для чисел Фибоначчи с отрицательными индексами остаются верными большинство нижеприведённых свойств.

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

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

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

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

В «нулевом» месяце, имеется пара кроликов (0 новых пар).
В первом месяце, первая пара производит на свет другую пару (1 новая пара).
Во втором месяце, обе пары кроликов порождают другие пары и первая пара погибает (1 новая пара).
В третьем месяце, вторая пара и две новые пары порождают в общем три новые пары, а старая вторая пара погибает (2 новые пары).

Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.

Пусть популяция за месяц n будет равна F(n). В это время, только кролики которые жили в месяце n-2 являются способными к размножению и производят потомков, тогда F(n-2) пар прибавится к текущей популяции F(n-1). Таким образом общее количество пар будет равно F(n) = F(n — 1) + F(n — 2).

Формула Бине

Формула Бине выражает в явном виде значение F_n как функцию от n:

$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\phi^n - (-\phi )^{-n}}{\phi - (-\phi )^{-1}}$

где $\phi=\frac{1 + \sqrt{5}}{2}$ — золотое сечение. При этом $\phi\,\!$ и $(-\phi )^{-1}=1-\phi\,\!$ являются корнями квадратного уравнения $x^2-x-1=0\,\!$ .

Из формулы Бине следует, что для всех $n\geqslant 0$ , F_n есть ближайшее к $\frac{\phi^n}{\sqrt{5}}\,$ целое число, то есть $F_n = \left\lfloor\frac{\phi^n}{\sqrt{5}}\right\rceil$ . В частности, справедлива асимптотика $F_n\sim \frac{\phi^n}{\sqrt{5}}$ .

Тождества

$F_1+F_2+F_3+\dots+F_n=F_{n+2}-1$

$F_1+F_3+F_5+\dots+F_{2n-1}=F_{2n}$

$F_2+F_4+F_6+\dots+F_{2n}=F_{2n+1}-1$

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

$F_1^2+F_2^2+F_3^2+\dots+F_{n}^2=F_nF_{n+1}$

$F_n^2+F_{n+1}^2=F_{2n+1}$

$F_{2n}=F_{n+1}^2-F_{n-1}^2$

$F_{3n}=F_{n+1}^3+F_n^3-F_{n-1}^3$

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

$F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}$

$F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_nF_{kn+1}$

$F_n^{}=F_lF_{n-l+1}+F_{l-1}F_{n-l}$

Числа Фибоначчи представляются значениями континуант на наборе единиц: $F_n = K_n(1,\dots,1)$ , то есть

$F_n = \det \begin{pmatrix} 1 &amp; 1 &amp; 0 &amp;\cdots &amp; 0 \\ -1 &amp; 1 &amp; 1 &amp; \ddots &amp; \vdots\\ 0 &amp; -1 &amp; \ddots &amp;\ddots &amp; 0 \\ \vdots &amp; \ddots &amp; \ddots &amp;\ddots &amp; 1 \\ 0 &amp; \cdots &amp; 0 &amp; -1 &amp; 1 \end{pmatrix}$

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

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

$F_{n+1} = (-i)^n U_n\left(\frac{-i}{2}\right) = (-i)^n T_n(-i)$

$F_{2n+2} = U_n\left(\frac{3}{2}\right) = T_n(3)$

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

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

Свойства

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (F_m,F_n) = F_(m,n). Следствия:
- F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n = 2). В частности, F_m делится на F₃ = 2 (то есть является чётным) только для m = 3k; F_m делится на F₄ = 3 только для m = 4k; F_m делится на F₅ = 5 только для m = 5k и т. д.
- F_m может быть простым только для простых m (с единственным исключением m = 4) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — $F_{19}=4181=37\cdot 113$ . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.

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

В 1964 Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: F₀ = 0² = 0, F₁ = 1² = 1, F₂ = 1² = 1, F₁₂ = 12² = 144. При этом для n=0,1,12 верно утверждение F_n = n².

$0 + x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}$

Множество чисел Фибоначчи совпадает с множеством положительных значений многочлена
z(x,y) = 2xy⁴ + x²y³ − 2x³y² − y⁵ − x⁴y + 2y,
на множестве неотрицательных целых чисел x и y ^[2].

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

Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом 300, последние три цифры — с периодом 1500, последние четыре — с периодом 15000, последние пять — с периодом 150000 и т. д.

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

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

В природе

Расстояния между листьями (или ветками) на стволе растения относятся примерно как числа Фибоначчи.

В культуре

См. также

Литература

Ссылки

Примечания

↑ [1] БСЭ]
↑ P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 193.

Wikimedia Foundation. 2010.

dic.academic.ru