Періодичність послідовності Фібоначчі по модулю
Розглянемо
послідовність Фібоначчі
по деякому модулю
. Доведемо, що вона є періодичною, і
причому період починається з
=1
(тобто передперіод містить тільки
).
Доведемо
це від супротивного. Розглянемо
пару чисел Фібоначчі, узятих по модулю
:
Оскільки
по модулю
може бути тільки
різних пар, то серед цієї послідовності
знайдеться як мінімум дві однакові
пари. Це вже означає, що послідовність
періодична.
Виберемо тепер серед усіх таких однакових пар дві однакові пари. Це вже означає, що послідовність періодична.
Виберемо
тепер серед усіх таких однакових пар
дві однакові пари з найменшими номерами.
Нехай це пари з деякими номерами
і
. Доведемо, що
. Дійсно, інакше для них знайдуться
попередні пари
і,
які, по властивості чисел Фібоначчі,
також дорівнюватимуть один одному.
Проте це суперечить тому, що ми вибрали
співпадаючі пари з найменшими номерами,
що і вимагалося довести.
Матрична формула для чисел Фібоначчі
Неважко довести матричну наступну рівність:
Але тоді,знаючи,що
отримуємо:
Таким чином, для знаходження n -го числа Фібоначчі потрібно звести матрицю P в степінь n .
Згадуючи,
що піднесення матриці до n-го
степеня можна здійснити за
, виходить, що n
-е число Фібоначчі можна легко вирахувати
за
з використанням тільки цілочисельної
арифметики.
Формула для n- го числа Фібоначчі Формула через радикали
Існує чудова формула, що названа іменем французького математика Бине(Binet), хоча вона була відома до нього Муавру(Moivre) :
При
цьому
і
є коренями квадратного рівняння
.
Цю формулу легко довести за індукцією, проте вивести її можна за допомогою поняття функцій, що її утворюють, або за допомогою рішення функціонального рівняння.
Оскільки
знаходимо, що при
Тому з формули Біне випливає, що для
всіх натуральних
,
є найближчим до
цілим числом,
. Зокрема, справедлива асимптотика
Втім, для практичного застосування в обчисленнях ці формули мало підходять, тому що вимагають дуже високої точності роботи з дробовими числами.