еще раз о числах фибоначчи
Aug. 31st, 2015 07:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНесколько лет назад я дал ссылку на элементарный вывод методами линейной алгебры формулы n-го числа Фибоначчи:
Вывод там был довольно красивый, но можно еще проще и элементарнее, не пользуясь даже понятиями собственного значения и детерминанта. На это мне тогда указали в комментариях (![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
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).
Вывод там был довольно красивый, но можно еще проще и элементарнее, не пользуясь даже понятиями собственного значения и детерминанта. На это мне тогда указали в комментариях (
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).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2015-08-31 04:18 pm (UTC)Для маленьких детей все понятно изложено в книжке "Возвратные последовательности", автора которой я за давностью лет запамятовал, но гугл подсказывает, что такая книжка есть у Маркушевича. Вероятно, она.
no subject
Date: 2015-08-31 04:21 pm (UTC)Я когда-то давно выводил из соображений, что зависимость от n степенная (ну, поскольку функция линейно зависит от своей производной), и надо только найти коэффициенты. Было довольно мучительно.
Это было еще до интернета, посоветоваться в тот момент было не с кем :(
no subject
Date: 2015-08-31 04:42 pm (UTC)no subject
Date: 2015-08-31 04:51 pm (UTC)- вместо слов "степенной ряд", более принято говорить "геометрическая прогрессия" - слово "ряд" используется когда речь идет о суммировании бесконечной последовательности, чего здесь нет.
- 'независимо от того, с каких двух чисел начинать ряд.." почти так; исключение - когда отношение первых двух чисел в точности равно (1-\sqrt{5})/2
no subject
Date: 2015-08-31 04:59 pm (UTC)no subject
Date: 2015-08-31 05:34 pm (UTC)no subject
Date: 2015-08-31 07:02 pm (UTC)no subject
Date: 2015-08-31 07:03 pm (UTC)no subject
Date: 2015-08-31 07:36 pm (UTC)no subject
Date: 2015-08-31 08:03 pm (UTC)no subject
Date: 2015-08-31 08:46 pm (UTC)no subject
Date: 2015-09-01 01:07 am (UTC)Потом, конечно, познакомившись с дифурами, стало понятно откуда тут все берется, но со школьными знаниями это была, конечно, магия.
Люблю интересненькое
Date: 2015-09-01 01:48 am (UTC)А почему обе формулы у Вас одинаковые?
Сходимость ряда отношений чисел прописана в алгоритме выстраивания ряда Фиобоначчи.
Почему Вы ещё не доказали эту очевидную закономерность?
Видимо размерность 2 определяется тем, что для запуска последовательности Фиобоначчи нужны только 2 числа.
Мне это напоминает выбор переменных Таккенса при определении размерности пространства вложения в дискретном анализе нелинейной динамики диссипативных систем.
no subject
Date: 2015-09-01 01:53 am (UTC)no subject
Date: 2015-09-01 01:58 am (UTC)Простите меня, пожалуйста, за наглость, но я попробую это сделать, когда взбрендит вдруг.
no subject
Date: 2015-09-01 04:25 am (UTC)no subject
Date: 2015-09-01 06:55 am (UTC)no subject
Date: 2015-09-01 07:07 am (UTC)no subject
Date: 2015-09-01 11:50 am (UTC)no subject
Date: 2015-09-05 03:37 pm (UTC)