ар предків даної пари (включаючи і вихідну), а нулями - всі інші місяці. Наприклад, послідовність 010010100010 встановлює таку генеалогію - Сама пара з'явилася наприкінці 11-го місяця, а її батьки - наприкінці 7-го, дід - Наприкінці 5-го, а прадід - Наприкінці другого. Вихідна пара кроликів зашифровується при цьому послідовністю 000000000000.
Ясно, що при цьому ні в однієї послідовності не можуть стояти дві одиниці підряд - щойно з'явилася пара не може, за умовою, принести приплід в наступному місяці. Крім того, при зазначеному правилі різним послідовностям відповідають різні пари кроликів, і назад, дві різні пари кроликів мають різну генеалогію raquo ;, так як, щоразу пара кроликів дає приплід, що складається також з однієї пари.
Встановлена ??зв'язок показує, що число n -послідовність, що володіють зазначеним властивістю, одно F (n).
Доведемо тепер, що
F (n)=+ + + ... +,
де, якщо n непарній, і, якщо n парне, іншими словами.
Є така комбінаторна задача про сходах: Скількома способами можна розставити n нулів і k одиниць так, щоб ніякі дві одиниці не стояли поруч raquo ;. Вирішення цього завдання можна зобразити у вигляді сходів, причому нуль означає місце, де ламана йде вправо, а одиниця - місце, де вона йде вгору (як показано на малюнку). При цьому, оскільки сходинок подвійної висоти на сходах немає, в послідовності не можуть йти дві одиниці поспіль. Таким чином, число послідовностей з n нулів і k одиниць буде дорівнює числу сходів, т. Е.. Число ж таких послідовностей, в які входить рівно k одиниць і n - k нулів, так само. Так як при цьому має виконуватися нерівність k? n - k +1, то k змінюється від 0 до. Застосовуючи правило суми, приходимо до співвідношення F (n)=+ + + ... +.
Дане рівність можна довести інакше: по властивості поєднань=+. Легко помітити, що послідовність чисел Фібоначчі має схожий властивістю: F (n)=F (n - 1) + F (n - 2).
Процес послідовних розбиття.
Зауважимо, що для вирішення комбінаторних задач часто застосовують такий метод - встановлюють для задачі рекурентне співвідношення і показують, що воно збігається з рекурентним співвідношенням для іншої задачі, рішення якої нам вже відомо. Якщо при цьому збігаються і початкові члени послідовностей в достатній числі, то обидва завдання мають однакові рішення.
Перерахуємо ще властивості, якими володіють числа послідовності Фібоначчі:
· Число Фібоначчі є найближче ціле число до, т. е. до n-му члену геометричній прогресії (, перший член якої, а знаменник дорівнює а. (ця властивість доводиться за допомогою запису формули Біне і встановлення того факту, що абсолютна величина різниці між членом послідовності Фібоначчі і членом даної прогресії менше. Якщо використовувати теорію меж, то легко можна показати, наскільки видозмінивши доказ цієї теореми, що
=0.
Користуючись доведеною теоремою, можна обчислювати числа Фібоначчі за допомогою таблиць логарифмів.
Обчислимо наприклад обчислимо.
a== 1,6180
=14?-=2,5762
=376,9
Найближче ціле число до 376, 9 є число 377, це і є.
При обчисленні чисел Фібоначчі з великими номерами ми вже не зможемо за таблицями логарифмів визначити всі цифри числа, а зможемо вказати тільки декілька перших цифр його, так що обчислення виявиться наближеним.
· Властивості чисел Фібоначчі, пов'язані з делимостью:
1. Сусідні числа Фібоначчі взаємно прості.
. Число Фібоначчі четно тоді і тільки тоді, коли його номер ділиться на 3.
. Число Фібоначчі ділиться на 3 тоді і тільки тоді, коли його номер ділиться на 4.
. Число Фібоначчі ділиться на 4 тоді і тільки тоді, коли його номер ділиться на 6.
. Число Фібоначчі ділиться на 5 тоді і тільки тоді, коли його номер ділиться на 5.
. Число Фібоначчі ділиться на 7 тоді і тільки тоді, коли його номер ділиться на 8.
. Число Фібоначчі ділиться на 16 тоді і тільки тоді, коли його номер ділиться на 12.
(Ці властивості можна довести, використовуючи властивості подільності чисел, алгоритм Евкліда, індукцію, а також властивість біноміальних коефіцієнтів: якщо р - просте, а k? 0 і k? p, то ділиться на р raquo ;).
· Добуток і частка двох будь-яких різних чисел Фібоначчі, відмінних від одиниці, ніколи не є числом Фібоначчі.
· виро...
