# 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.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.