Recursion Formulas

I do not know if I ever wrote about this. But it is a well known theory, anyways. To find a formula for the Fibonacci numbers

\(F_{n+1} = F_n + F_{n-1}, \quad F_0 = 0, \quad F_1 = 1\)

you can use the „Ansatz“

\(F_n = c^n\)

you will immediately find that c must satisfy

\(c^2 = c + 1\)

The two solutions for this equation can both generate the recursion formulas as well as any linear combination of them. So our Ansatz yields

\(F_n = a c_1^n + b c_2^n = a \left(\dfrac{1+\sqrt{2}}{2}\right)^n + b \left(\dfrac{1-\sqrt{2}}{2}\right)^n\)

Observe the logic that we followed here! All we know by know is that if F(n) is defined by this formula, it will satisfy the recursion formula for the Fibonacci sequence. On the other hand, it is easy to find a and b such that F(0)=0, F(1)=1. Then we know that we have indeed found the correct formula for the sequence. I.e.,

\(F_n = a c_1^n + b c_2^n = \dfrac{1}{\sqrt{5}} \left( \left(\dfrac{1+\sqrt{2}}{2}\right)^n – \left(\dfrac{1-\sqrt{2}}{2}\right)^n\right)\)

We have also shown that any sequence which satisfies the recursion must be of that form with proper constants a and b. This is so, since we can determine a and b for any start values.

Due the fact that c(2) is between -1 and 0, we get

\(F_n = \text{round } \dfrac{1}{\sqrt{5}} \left(\dfrac{1+\sqrt{2}}{2}\right)^n\)

Now, if we take other start values, what happens? E.g., consider the numbers

\(L_n = \left(\dfrac{1+\sqrt{2}}{2}\right)^n + \left(\dfrac{1-\sqrt{2}}{2}\right)^n\)

The start values are then L(0)=2 and L(1)=1. We simply get another integer sequence. And we get the strange fact that

$latex \left(\dfrac{1+\sqrt{2}}{2}\right)^n$

gets closer and closer to integers. This has been observed by Yves Meyer and mentioned in a blog post recently by J. D. Cook. So I came to write this short article. The difference, computed in Euler Math Toolbox, is as follows

>p1 = (1+sqrt(5))/2
 1.61803398875
>p2 = (1-sqrt(5))/2
 -0.61803398875
>n=0:19; longest (p1^n)'
                       1 
       1.618033988749895 
       2.618033988749895 
        4.23606797749979 
       6.854101966249686 
       11.09016994374948 
       17.94427190999916 
       29.03444185374864 
       46.97871376374781 
       76.01315561749645 
       122.9918693812443 
       199.0050249987407 
        321.996894379985 
       521.0019193787257 
       842.9988137587108 
       1364.000733137437 
       2206.999546896147 
       3571.000280033584 
       5777.999826929732 
       9349.000106963316 
>p1^n+p2^n
 [2,  1,  3,  4,  7,  11,  18,  29,  47,  76,  123,  199,  322,  521,
 843,  1364,  2207,  3571,  5778,  9349]

The difference to the next integer is of course a power of p2 goes to zero geometrically fast.

22. März 2017 von mga010
Kategorien: English, Euler | Schreibe einen Kommentar

Schreibe einen Kommentar

Pflichtfelder sind mit * markiert