![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
еще раз о числах фибоначчи
Aug. 31st, 2015 07:01 pmНесколько лет назад я дал ссылку на элементарный вывод методами линейной алгебры формулы 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).
