Изменения

пример: 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%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D1%8E%D0%BA%D0%B0 Числа Люка]

==Фибоначева Система Исчислениясчисления=='''Фибоначчева Фибоначчива Система исчеслениясчисления''' - позиционная система исчесления счисления для целых чисел на основе чисел Фибоначчи.

Если для алгоритма Евклида требуются 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 году