числа фибоначчи (математическое)

[avva]

Я не помню, где я впервые увидел формулу для n-го числа Фибоначчи



Думаю, это было в одной из книг Мартина Гарднера. Помню, что она потрясла мое воображение, и я не мог понять, "откуда они знают", что в таких высоких степенях иррациональных чисел вся иррациональность в итоге сбрасывается, и получается натуральное число. Я поверил в это, но доказательство этого казалось совершенно недостижимым, какой-то магией. Я не понимал, что нужно знать, чтобы уметь такое найти.

И как-то получилось, что я этого доказательства так и не видел ни разу, и остался - не задумываясь об этом всерьез - при своем впечатлении, что это "очень сложно".

Поэтому меня совершенно ошеломило увиденное случайно вчера элементарное доказательство этой формулы методами линейной алгебры. Я понимаю, что тем, кто не учил линейную алгебру в университете, это никак не поможет, но поверьте мне тогда на слово - это очень простая математика, самый первый шаг после школьной, самое простое, что можно назвать "высшей математикой". Подробное доказательство (по-английски) есть здесь. Золотое сечение (число φ = (√5+1)/2) возникает в нем при подсчете собственных значений элементарной матрицы 2x2 из единичек и нулей.

---

Раз уж зашла речь о числах Фибоначчи, поделюсь еще чем-то, что узнал о них пару лет назад - не помню, писал ли тут. Многие знают, что последовательность Фибоначчи, а также число φ, золотое сечение, встречаются в природе в множестве разных процессов, а заодно и в античном искусстве и архитектуре. Так вот, почти все утверждения такого рода неверны - это очень распостраненный миф, который почти всегда оказывается неточной подгонкой под желаемый результат (необязательно осознанной, конечно). Подробная и очень интересная статья об этом, опять-таки по-английски: Fibonacci Flim-Flam. Еще одна статья на ту же тему, менее подробная и в основном о золотом сечении: The Myth That Will Not Go Away.

Comments

[alex-vinokur.livejournal.com]

Huffman codes and Fibonacci numbers
http://groups.google.com/group/comp.graphics.algorithms/browse_thread/thread/3608b317d83eddb0?tvc=2


Fibonacci connection between Huffman codes and Wythoff array
http://arxiv.org/abs/cs/0410013

[shultz-flory.livejournal.com]

Я впервые встретил доказательство у Дональда Кнута в «Конкретной математике».

[allocco.livejournal.com]

Так ведь доказательство, основанное на определении (рекуррентном соотношении), ещё проще — там не надо знать матриц, а надо лишь уметь решать квадратное уравнение.

даже

[a-shen.livejournal.com]

и квадратного уравнения не надо - надо заметить, что два первых члена, вычисленные по этой формуле, равны 1 и 1 и что каждый следующий член, вычисленный по формуле, равен сумме двух предыдущих...

[aa-kir.livejournal.com]

Ну да. Именно так меня этому учили в школе.

[vlad_suh]

Кстати да, отношения золотого сечения - это корни уравнения, которое описывает их свойства.

[whichferdinand.livejournal.com]

Я очень давно знал про эту формулу (и помнил, что так что-то большое и сложное с радикалами), но только относительно недавно узнал, что fib(n) = round(phi^n / sqrt(5)) (только округляют вниз, а не вверх). Меня удивило, что на самом деле, формула не большая и не страшная.

[salas.livejournal.com]

только округляют вниз, а не вверх
Всё-таки не вниз, не вверх, а к ближайшему.

[randomisator.livejournal.com]

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

[buddha239.livejournal.com]

Я как-то сам эту формулу придумал - классе в 7ом.:)

[eterevsky.livejournal.com]

Вообще это достаточно простой факт. Легко доказать более общее утверждение:

Если у нас есть рекуррентная последовательность вида x_n = a_1 * x_(n-1) + a_2 * x_(n-2) + ... + a_k * x_(n-k), то x_n представляется как линейная комбинация n-ых степеней корней многочлена t^n - a_1 * t^(n-1) - a_2 * t^(n-2) - ... - a_(k-1) * t - a_k.

И даже если не знать этого, то понять что результат в формуле для числа Фибоначчи будет целым очень легко: достаточно заметить, что если раскрыть скобки по биному Ньютона, то все иррациональные члены сократятся, а целые -- наоборот сложатся.

[kot-begemot.livejournal.com]

если раскрыть скобки по биному Ньютона, то все иррациональные члены сократятся, а целые -- наоборот сложатся.
Именно так.

[dmpogo.livejournal.com]

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

Именно, это-то как раз очевидно.

[eterevsky.livejournal.com]

*Многочлен, естественно k-й степени, а не n-ой:

t^k − a₁t^k−1 − ... − a_k−1t − a_k

[theshadeck.livejournal.com]

Поразительно! В сегодняшней ленте - 2 свидетельства того, что мои скучннейшие технионовские преподы делали прикольные вещи. Вот тут Ирад Явне зажигает, а в статье по ссылке упоминается Марио Ливио в качестве развенчателя золотосечного мифа (правда, Ливио я уже не застал, но на видео его лекции видел).

[kot-begemot.livejournal.com]

Интересно, а вот в техническом анализе на бирже известные Fibonacci Levels - тоже надуманные, или как? Мне почему-то кажется, что нет, хотя я могу ошибаться.

[rukenau.livejournal.com]

В статье, на которую Авва ссылку дал, есть сноска с ответом, кажется, как раз на Ваш вопрос: http://www.cs.ucl.ac.uk/staff/D.Quercia/others/numbers.pdf.

[gaz-v-pol.livejournal.com]

Меня тоже в своё время поразило это явление. Много возился с этими формулами. Можно немного видоизменить условие Фибоначчи так, что числа в явной форуме будут мнимыми. Например если F(0)=F(1)=1 и



то явная формула такая:




Разрешим использовать дроби. Пусть F(0)=3, F(1)=-1/2 и



Казалось бы, ну дроби и дроби, чего тут ждать удивительного? А вылезает ... тригонометрия. Явная формула:

[buddha239.livejournal.com]

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

[michk.livejournal.com]

Ну вот, ещё один детский миф развенчан. Как теперь жить?

[bakhtin.livejournal.com]

Один из мотивирующих примеров в линейной алгебре. Наряду с PageRank'ом.

[gemelen]

Другой интересный и более редкий способ получения этой и подобных формул - применение дискретного преобразования Лапласа при решении разностных уравнений, в рамках операционного исчисления.
В данном случае, формула для члена последовательности есть решение уравнения f(n+2)-f(n+1)-f(n)=0 при f(0)=1 и f(1)=1.

[janatem.livejournal.com]

Меня (видимо, в несколько более позднем возрасте) удивил метод вывода n-го члена для любых линейных реккурентных соотношений вида A(n) = a_1 A(n-1) + ... + a_k A(n-k): нужно составить характеристический многочлен, найти все его корни и составить линейную комбинацию n-ых степеней этих корней (это если все корни различны, а если есть кратные, то чуть иначе). Удивительным мне казалось, что этот метод работает на практике, т.е., применив его на примере, можно было получить решение, причем с доказательством (для данного конкретного примера). Найти доказательное обоснование метода мне тогда не удалось, потом как-то забылось. А сейчас вижу, что вроде бы из доказательства по ссылке для последовательности Фибоначчи легко получить универсальное доказательство корректности метода.

О, я сейчас вспомнил, что в курсе дифуров был в аналогичный метод решения линейного ОДУ произвольного порядка с постоянными коэффициентами. Уверен, что между доказательствами обоих методов должен быть изоморфизм.

[shuffle81.livejournal.com]

Уверен, что между доказательствами обоих методов должен быть изоморфизм.

Ну в общем-то, это близкие вещи, хотя не вполне "изоморфные". Формула линейной рекурренты получается из возведения матрицы в степень, формула для решения ОДУ - из экспоненты матрицы (линейное уравнение порядка n на функцию f эквивалентно матричному уравнению v'=Av на вектор v=(f,f',...,f^{(n-1)}), ну а такое как раз решается через экспоненту).

ровесники Ильича :)

[falcao.livejournal.com]

Мне всегда казалось, что самый простой и элементарный вывод формулы основан на подборе геометрических прогрессий, удовлетворяющих рекуррентному соотношению. "Золотое сечение" там возникает сразу, и выясняется, что таких прогрессий ровно две. Ясно, что все их линейные комбинации тоже удовлетворяют уравнениям, и за счёт двух "свободных" констант из них выбираются те, которые удовлетворяют "начальным условиям".

Мне кажется, это проще, чем диагонализация матриц, и применение линейной алгебры тут одно из наиболее "эффектных" (на "элементарном" материале).

Что касается "мифов", то главным из них является миф о самом "Фибоначчи". Нетрудно поискать информацию по этому поводу в google books. Оказывается, что "пятнадцатитомник" Великого Самоучки XIII века был "найден" только в 1758 году во Флоренции неким человеком по фамилии Tozzetti. После чего прошло около 100 лет, и "труд" издали. Далее начался "бум", в Пизе открыли памятник "гению". А сами числа назвал в честь Фибоначчи француз Эдуард Люка в 1870 году. До этого их никто так не называл, и когда Бине выводил свою формулу, то этого имени никто вообще не использовал.

Re: ровесники Ильича :)

[markvs.livejournal.com]

Мне кажется, это зависть: ему памятник в Пизе поставили, а тебе пока нет.

[potan.livejournal.com]

Мне тоже подход с линалом больше всего нравится. Нравится своей вычислимостью - работать с матрицами проще, чем с иррациональными числами.

[oblomov-jerusal.livejournal.com]

Была какая-то популярная книжка про числа Фибоначчи (возможно эта), в ней доказывалась эта формула

[dmitriy mandel (from livejournal.com)]

Вот совершенно очаровательное видео именно на тему чисел Фибоначчи в природе. Оно в трех частях, и если часть первая просто хороша стилистически, то вторая и особенно третья иллюстрируют некоторые новые для меня идеи.



Part 2: http://youtu.be/lOIP_Z_-0Hs
Part 3: http://youtu.be/14-NdQwKz9w

(Вообше vihart молодец, у неё почти всё интересно получается.)