?

Log in

еще раз о числах фибоначчи - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

еще раз о числах фибоначчи [авг. 31, 2015|07:01 pm]
Anatoly Vorobey
[Tags|]

Несколько лет назад я дал ссылку на элементарный вывод методами линейной алгебры формулы n-го числа Фибоначчи:



Вывод там был довольно красивый, но можно еще проще и элементарнее, не пользуясь даже понятиями собственного значения и детерминанта. На это мне тогда указали в комментариях (falcao и кто-то еще, кажется), но я этого тогда не понял, а сегодня до меня наконец дошло. Примерно так:

Мы рассматриваем бесконечные последовательности действительных чисел (a0, a1, a2...) в которых выполняется правило Фибоначчи: каждый член равен сумме двух предыдущих. В частности, последовательность Фибоначчи отвечает этому правилу: (0, 1, 1, 2, 3, 5, 8...), но можно начать и с двух других любых чисел, например (10, 80, 90, 170, 260...). Понятно, что если у двух последовательностей такого типа совпадают первые два члена, то и все остальные совпадают, потому что правило сложения их жестко определяет.

Попытаемся найти последовательность такого типа особо простого вида, состоящую только из степеней какого-то числа τ: (τ^0, τ^1, τ^2, τ^3...). Чтобы такая последовательность выполняла закон, нужно как минимум чтобы третий член был суммой первых двух: τ^2 = τ^1+τ^0, то есть τ^2-τ-1 = 0. С другой стороны, этого требования достаточно, т.к. для дальнейших членов правило оказывается таким же, только умноженным еще на какую-то степень tau. У этого уравнения есть два решения: τ1 = (1+sqrt(5)/2) и τ2 = (1-sqrt(5))/2. Соответственно, степенные ряды, составленные из степеней τ1 и τ2, отвечают правилу Фибоначчи.

Понятно, что любая линейная комбинация двух последовательностей, отвечающих правилу Фибоначчи, тоже отвечает правилу Фибоначчи. Т.е. взяв любые действительные a,b мы можем составить последовательность, в которой n-й член будет a*τ1^n + b*τ2^n, и она будет отвечать правилу Фибоначчи. Попробуем так подобрать a и b, чтобы первые два члена получились 0,1. Сразу видим, что из равенства нулю при n=0 следует a=-b, и пользуясь теперь только a и -a в равенстве 1 для n=1, находим, что a=1/sqrt(5). Значит, ряд



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

(линейная алгебра: векторное пространство последовательностей, отвечающих правилу Фибоначчи, имеет размерность 2, потому что первые два члена определяют всю последовательность. А найденные нами два степенных ряда τ1^n и τ2^n линейно независимы в этом пространстве, опять-таки глядя на первые их два члена. Поэтому из соображений базиса мы точно знаем, что есть формула для общего члена последовательности Фибоначчи - или любой другой последовательности, выполняющей правило - в терминах этих рядов. Но для данного простого вывода нет даже надобности это заключать, можно просто попробовать решить, как написано выше.

Зато из этих соображений сразу следует другой казавшийся мне в детстве "мистическим" результат: что независимо от того, с каких двух чисел начинать ряд, частное двух соседних членов будет постепенно стремиться к phi = (1+sqrt(5))/2. Любую последовательность можно представить как линейную комбинацию степенных рядов τ1^n и τ2^n с какими-то коэффициентами a,b, и рассмотрев частное n+1-го и n-го членов, легко представить его как сумму τ1 и остатка, который стремится к 0 при любых a,b).
СсылкаОтветить

Comments:
[User Picture]From: hyperpov
2015-08-31 04:18 pm
Оно так просто, если корни не случились кратными. А если бы случились, то чуть менее просто.
Для маленьких детей все понятно изложено в книжке "Возвратные последовательности", автора которой я за давностью лет запамятовал, но гугл подсказывает, что такая книжка есть у Маркушевича. Вероятно, она.
(Ответить) (Thread)
[User Picture]From: mopexod
2015-08-31 04:21 pm
Красивый вывод.
Я когда-то давно выводил из соображений, что зависимость от n степенная (ну, поскольку функция линейно зависит от своей производной), и надо только найти коэффициенты. Было довольно мучительно.
Это было еще до интернета, посоветоваться в тот момент было не с кем :(
(Ответить) (Thread)
[User Picture]From: utnapishti
2015-08-31 08:46 pm
"Нечестное" предположение о том, что последовательность Фибоначчи - степенная, часто мотивируют тем, что n-ный элемент меньше чем 2^n, но больше, чем (sqrt(2))^n (начиная с какого-то, не очень далёкого, места; легко доказывается по индукции).
(Ответить) (Parent) (Thread)
[User Picture]From: mopexod
2015-09-01 07:07 am
Это было в самом начале института. Я же не математик, а инженер-физик: для меня всё, у чего что производная пропорциональна функции, - экспонента.
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2015-09-01 11:50 am
Ну да, так ещё честнее. Например, можно сказать, что последовательность разностей является сдвигом самой последовательности. Прежде всего, это значит, что разности никогда не обнулятся, а значит - последовательность Фибоначчи не полиномиальная. Далее, из простых последовательностей это больше всего похоже на 2^n, поэтом мы ожидаем экспоненциальную последовательность.
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2015-08-31 04:42 pm
В детстве я читал какую-то книжку про числа Фибоначчи, там был этот вывод
(Ответить) (Thread)
[User Picture]From: michk
2015-08-31 07:03 pm
Искатели необычных автографов?
(Ответить) (Parent) (Thread)
[User Picture]From: aa_kir
2015-08-31 04:51 pm
Мелкие поправки:
- вместо слов "степенной ряд", более принято говорить "геометрическая прогрессия" - слово "ряд" используется когда речь идет о суммировании бесконечной последовательности, чего здесь нет.

- 'независимо от того, с каких двух чисел начинать ряд.." почти так; исключение - когда отношение первых двух чисел в точности равно (1-\sqrt{5})/2

(Ответить) (Thread)
[User Picture]From: avva
2015-08-31 04:59 pm
Ага, спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: hyperpov
2015-08-31 07:02 pm
А еще есть такой способ вставлять формулы, например:
(Ответить) (Parent) (Thread)
[User Picture]From: begemu
2015-09-01 01:53 am
Геометрическая прогрессия - долго произносить. Этот термин используют в школе и на первых курсах вузов. Степенной ряд - употребляется чаще в научных работах.
(Ответить) (Parent) (Thread)
[User Picture]From: hyperpov
2015-09-01 06:55 am
Употребляется, но совсем в другом смысле. Неплохо иногда прочесть коммент, на который отвечаете.
(Ответить) (Parent) (Thread)
[User Picture]From: alaev
2015-08-31 05:34 pm
Да, доходчиво.
(Ответить) (Thread)
[User Picture]From: yakov_a_jerkov
2015-08-31 07:36 pm
Спасибо, я не знал этого. И Вы очень доступно написали.
(Ответить) (Thread)
[User Picture]From: happy_husband
2015-08-31 08:03 pm
Красиво. Буквально сегодня думал про числа Фибоначчи и золотое сечение. Подумалось, что должны быть формула для чисел Ф, похожая на формулу ЗС. И вот внезапно читаю такое. Совпадение звучит неправдоподобно, но врать смысла нет.
(Ответить) (Thread)
[User Picture]From: nefedor
2015-09-01 01:07 am
Я этот вывод прочитал в старших классах школы когда готовился к экзаманам. Он меня порязил смелым предположением о степенном характере зависимости, остальное - дело примитивной техники, а вот это предположение мне показалось чем-то средним между волшебством и жульничеством.
Потом, конечно, познакомившись с дифурами, стало понятно откуда тут все берется, но со школьными знаниями это была, конечно, магия.

Edited at 2015-09-01 01:08 (UTC)
(Ответить) (Thread)
[User Picture]From: begemu
2015-09-01 01:48 am

Люблю интересненькое

А почему до сих пор не сделали компьютер на числах Фиобоначчи?
А почему обе формулы у Вас одинаковые?
Сходимость ряда отношений чисел прописана в алгоритме выстраивания ряда Фиобоначчи.
Почему Вы ещё не доказали эту очевидную закономерность?
Видимо размерность 2 определяется тем, что для запуска последовательности Фиобоначчи нужны только 2 числа.
Мне это напоминает выбор переменных Таккенса при определении размерности пространства вложения в дискретном анализе нелинейной динамики диссипативных систем.
(Ответить) (Thread)
[User Picture]From: begemu
2015-09-01 01:58 am
Надо будет поизвращаться и вывести как-нибудь на досуге. Думаю, что ничего особо сложного здесь нет.
Простите меня, пожалуйста, за наглость, но я попробую это сделать, когда взбрендит вдруг.
(Ответить) (Thread)
[User Picture]From: xaxam
2015-09-01 04:25 am
Линейная алгебра и была "придумана" (сформулирована) ровно для того, чтобы подобные рассуждения становились автоматическими. Плохо, что (хотя бы на уровне подобных примеров) она совершенно отсутствует в школьной программе.
(Ответить) (Thread)
[User Picture]From: nu57
2015-09-05 03:37 pm
Здорово, спасибо.
(Ответить) (Thread)