Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

еще раз о числах фибоначчи

Несколько лет назад я дал ссылку на элементарный вывод методами линейной алгебры формулы 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).
Tags: математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 20 comments