Числа Фибоначчи

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Более формально, последовательность чисел Фибоначчи задаётся линейным рекуррентным соотношением:

Иногда числа Фибоначчи рассматривают и для отрицательных значений , как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: :

n −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10
−55 34 −21 13 −8 5 −3 2 −1 1 0 1 1 2 3 5 8 13 21 34 55

Легко заметить, что .

Происхождение[править | править вики-текст]

Страница Книги абака (лат. Liber abaci) Фибоначчи из Национальной центральной библиотеки Флоренции.
В правом блоке демонстрируется последовательность Фибоначчи.
Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами, а значения красным цветом индо-арабскими цифрами

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

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

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

  • В начале первого месяца есть только одна новорожденная пара (1).
  • В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1)
  • В конце второго месяца первая пара рождает новую пару и опять спаривается (2)
  • В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3)
  • В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5)

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

Формула Бине[править | править вики-текст]

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

где  — золотое сечение. При этом и являются корнями характеристического уравнения .

Из формулы Бине следует, что для всех , есть ближайшее к целое число, то есть . В частности, при справедлива асимптотика .

Формула Бине может быть аналитически продолжена следующим образом:

При этом соотношение выполняется для любого комплексного числа z.

Тождества[править | править вики-текст]

Геометрическое доказательство формулы для суммы квадратов первых n чисел Фибоначчи[2].

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

  • Числа Фибоначчи представляются значениями континуант на наборе единиц: , то есть
, а также ,
где матрицы имеют размер , i — мнимая единица.
  • Для любого n,

Свойства[править | править вики-текст]

  • Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, то есть . Следствия:
    • делится на тогда и только тогда, когда делится на (за исключением ). В частности, делится на (то есть является чётным) только для ; делится на только для ; делится на только для и т. д.
    • может быть простым только для простых (с единственным исключением ). Например, число простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
  • Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен имеет корни и .
  • Отношения являются подходящими дробями золотого сечения и, в частности,
  • Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы
    .
  • В 1964 году Дж. Кон (J. H. E. Cohn) доказал,[3] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
    , , , .
  • Производящей функцией последовательности чисел Фибоначчи является:
  • Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена
на множестве неотрицательных целых чисел x и y.[4]
  • Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
  • Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:
    1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)
    • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
  • Натуральное число N является числом Фибоначчи тогда и только тогда, когда или является квадратом.[5]
  • Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.[6]
  • Число Фибоначчи равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом равно количеству таких кортежей, начинающихся с нуля, а  — начинающихся с единицы.
  • Число 0,112358132134… (после запятой записаны подряд идущие числа Фибоначчи) является иррациональным.[источник не указан 937 дней]

Вариации и обобщения[править | править вики-текст]

В других областях[править | править вики-текст]

Существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространенный миф, который часто оказывается неточной подгонкой под желаемый результат[7][8].

В природе[править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Числа Фибоначчи // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
  2. Фибоначчи числа // Энциклопедический словарь юного математика / Сост. Савин А. П.. — 2-е изд. — М.: Педагогика, 1989. — С. 312—314. — 352 с. — ISBN 5715502187.
  3. J H E Cohn. Square Fibonacci Numbers Etc, стр. 109–113.
  4. P. Ribenboim. The New Book of Prime Number Records. — Springer, 1996. — С. 193.
  5. Ira Gessel Problem H-187 // Fibonacci Quarterly. — 1972. — Т. 10. — С. 417–419.
  6. В. Серпинский. Задача 66 // 250 задач по элементарной теории чисел. — М.: Просвещение, 1968. — 168 с.
  7. Fibonacci Flim-Flam (англ.)
  8. The Myth That Will Not Go Away (англ.)
  9. 1 2 .Золотое сечение в природе
  10. Числа Фибоначчи
  11. Числа Фибоначчи
  12. Акимов О. Е. Конец науки.
  13. Г. Манукян. Поэзия чисел Фибоначчи

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]