Изменения

где $n>=2$ <br>пример: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …<br> Числа также числа Фибоначчи задаются можно обобщить на произвольные начальные значения $F_1$ и $F_2$ например [https://ru.wikipedia.org/wiki/%D0%9BA7%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5B0_%D0%B49B%D0D1%BE8E%D0%B2BA%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C|линейным рекуррентным соотношениемЧисла Люка] $F_1$=1, $F_2$=1, $F_n$=$F_{n-1}$ + $F_{n-2}$, где $n>=2$

[[Файл:0_L7N1ispU7cFS4HV8.jpeg|200px|thumb|спираль золотого сечения]][https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B5_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5| Золотое сечение] может быть выражено, с помощью чисел Фибоначчи: $$\Phi=\lim\limits_{x \to \infty} \dfrac{F_{n+1}/}{F_n}$$

==Формула БиннеБине==

$F_n=\dfrac{\phi^n - (-\phi)^{-n}}{2\phi - 1}$,где $<br>$\phi=\dfrac{\sqrt5 + 1}{2} $ - золотоесечение===Доказательство===:$\psi=\quad сечениеdfrac{1-\sqrt{5}}{2}=-\dfrac{1}{\phi}$Докажем формулу по индукции. Для этого нужно доказать равенство $\phi^n - \psi^n + \phi^{n+1} - \psi^{n+1}= \psi^{n+2} - \phi^{n+2}$,которое после преобразования превращается в $\phi^n(1 - \phi - \phi^2) = \psi^n(1 - \psi - \psi^2)$. Осталось заметить, что оба числа, $\phi$ и $\psi$, служат корнями многочлена $1 - a - a^2$, так что выражения в скобках в обеих частях равенства обращаются в ноль одновременно. Вот и доказан индуктивный переход. Что же касается базы индукции, то она совершенно очевидна при n=0 и n=1.

 ==ТоржестваТождества==* {{Теорема|statement=$\displaystyle\sum_{i=1}^{n} F_i=F_{n+2} - 1$|Hiden|proof===Доказательство===<p style="text-align:justify;">

:$\displaystyle\sum_{i=1}^{n+1} F_i = F_{n+3} - 1$<br>ч.т.д}}</p>{{Теорема|statement=$\displaystyle F_{1}+F_{3}+F_{5}+\dots +F_{2n-1}=F_{2n}$|proof=}} {{Теорема|statement=$\displaystyle F_{2}+F_{4}+F_{6}+\dots +F_{2n}=F_{2n+1}-1$|proof=}} {{Теорема|statement=$\displaystyle\sum_{i=1}^{2n -1} F_i^2=F_{n}F_{n+1}$|proof=}} {{Теорема|statement=$F_n^2 + F_{n+1}^2=F_{2n+1}$|proof=}}

* $\displaystyle\sum_{i=1}^{2n -1} F_i=F_{2n}$Теорема* $F_2 + F_4 + F_6 + ... + F_{2n} |statement= F_{2n-1} -1$* $\displaystyle\sum_{i=1}^{2n -1} F_i^2=F_{n}F_{n+1}$*$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}=\sum_{i=0}^{n} \binom{n-1}{i}} $<p>|proof=}}

все формулы легко доказываются по формуле Бинне</p>==Фибоначева Система Исчислениясчисления=='''Фибоначчива Система исчеслениясчисления''', в которой вес $n$-ного разряда равен $F_n$:позиционная система счисления для целых чисел на основе чисел Фибоначчи.:'''1010''' = 0*F_0 + 1*F_1 + 0*F_2 + 1*F_3$==Представление натуральных чисел===

||statement=Любое натуральное неотрицательное целое число $\displaystyle a$ можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи последовательностью битов $…ε_k…ε_4ε_3ε_2$ $\varepsilon _{k}\in \{0,1\}$ так, чтобы в этом представлении что $\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}$, причём последовательность ${ε_k}$ содержит лишь конечное число единиц, и не оказалось двух имеет пар соседних чисел из последовательности Фибоначчиединиц:$\displaystyle \forall k\geq 2\colon (\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)$.

'''Докажем воинственность единственность представления'''

{{Лемма '''Лемма''': |statement=Сумма элементов любого непустого множества различных подпоследовательности чисел Фибоначчи (без последовательных), с максимальным числом Fj меньших $F_j$ строго меньше, чем следующее число Фибоначчи $F_j + 1F_j$.|proof=Доказательство следует из Тождеств Лемма доказывается индукцией по j.}}

Докажем от противного, что хотя бы одно из множеств '''S′''' и '''T′''' пусто. Предположим, что это не так, т. е. что '''S′''' и '''T′''' оба непусты, и пусть наибольший элемент '''S′''' есть $F_s$, а наибольший элемент '''T′''' есть $F_t$. Поскольку '''S′''' и '''T′''' не содержат общих элементов, $F_s ≠ F_t$. Без потери общности предположим, что $F_s < F_t$. Тогда по лемме сумма элементов '''S′''' строго меньше, чем $F_s F_{s+ 11}$, т. е. строго меньше, чем $F_t$, поскольку сумма элементов '''T′''' не меньше, чем $F_t$. А это противоречит тому, что '''S′''' и '''T′''' имеют одинаковую сумму элементов. Следовательно, либо '''S′''', либо '''T′''' пусто.

Если для алгоритма Евклида требуются N шагов для пары натуральных чисел $a > b > 0$, наименьшие значения a и b, для которых это выполняется — числа Фибоначчи $F_{N+2}$ и $F_{N+1}$ соответственно. Тогда, если алгоритм Евклида требует N шагов для пары чисел $(a,b)$, где $a > b$, выполняются следующие неравенства $a ≥ F_{N+2}$ и $b ≥ F_{N+1}$. Доказать это можно по математической индукции. Если N = 1, тогда a делится на b без остатка. Наименьшие натуральные числа, для которых это верно, равны b = 1 и a = 2, соответственно F2 и F3. Предположим теперь, что результат выполняется для всех значений N до M − 1. Первый шаг алгоритма Евклида с M шагами $a = q0b q_0b + r0r_0$, и алгоритм Евклида для пары чисел $(b,r0r_0)$, где b > r0, требует M − 1 шагов. По предположению индукции имеем $b ≥ F_{M+1}$ и $r0 r_0 >= F_M$. Следовательно, $a = q_0b + r_0 ≥ b + r_0 ≥ F_{M+1} + F_M = F_{M+2}$, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году == Источники информации ==*[http://ru.wikipedia.org/wiki/Числа_Фибоначчи {{---}} Числа Фибоначчи]*[http://ru.wikipedia.org/wiki/Алгоритм_Евклида {{---}} Алгоритм Евклида]