Generalized Fibonacci Sequence
While re-reading for
the thousandth time (!) section 1.2 of SICP, I have come across the following
exercise:
"Exercise 1.13:*
Prove that _Fib_(n) is the closest integer to
[phi]^n/[sqrt](5), where [phi] = (1 + [sqrt](5))/2. Hint:
Let [phip]
= (1 - [sqrt](5))/2. Use induction and the definition of the Fibonacci numbers (see section *Note 1-2-2::) to prove that _Fib_(n) = ([phi]^n -
[phip]^n)/[sqrt](5)." The notation is a bit crazy. For clearer notation of Fibonacci sequence and related concepts, see: http://www.geocities.com/hjsmithh/Fibonacc/FibWhat.html
= (1 - [sqrt](5))/2. Use induction and the definition of the Fibonacci numbers (see section *Note 1-2-2::) to prove that _Fib_(n) = ([phi]^n -
[phip]^n)/[sqrt](5)." The notation is a bit crazy. For clearer notation of Fibonacci sequence and related concepts, see: http://www.geocities.com/hjsmithh/Fibonacc/FibWhat.html
To prove this one,
first, we need to prove that the rule applies to the base case when n equals
1. This is trivial:
(define phi (/ (+ 1
(sqrt 5)) 2))
(define (power
result base r) (if (= r 0) result (power (* result base) base (- r
1))))
(define (fib n)
(round (/ (power 1 phi n) (sqrt 5))))
Now, type:
Now, type:
(fib
1)
You will receive 1.0
as the answer. Yes, that does not look like an integer. You have to
put up with these silly issues of mine until I get better at
Scheme.
The second step is
to assume that that the rule applies to all the cases up to n and then, based on
this assumption, we prove that the rule applies even for
n+1.
This is easy to see
that
fib(k) =
phi*f(k-1)
Therefore, we can
write
fib(n+1) = fib(n) +
fib(n-1) and
fib(n+1) =
phi*fib(n-1) + fib(n-1)
In other words, the
RHS equals:
fib(n-1)*(1+phi)
We also know
that
fib(n+1) = phi^2 *
fib(n-1)
Equating both the
RHS's and canceling fib(n-1), we get
phi^2 =
1+phi
The above is nothing
but the Fibonacci relation!
After that, I have
spent a bit more time on the last equation.
On the RHS of the
last equation, I have changed the number from 1 to 2.
In this case,
solving the resulting quadratic equation, we get phi equals 2. What does
this mean in terms of the sequence? Basically, we add the last but one
term twice.
fib2(n) = fib2(n-1)
+ 2* fib2(n-2)
If we start with 1
and 1, we obtain:
1, 1, 3, 5, 11, 21,
43 ...
If w look at it
carefully, we notice that basically that we are doubling the previous term and
either adding or subtracting 1.
If we had started
with 1 and 2, we would have got the powers of 2.
Now, if we increase
that number to 6, we get powers of 3. For this, we need to start with 1
and 3.
fib3(n) = fib3(n-1)
+ 6 * fib3(n-2)
However, if we start
with 1 and 1, we get:
1 1 7 13 55 133
...
The relation among
the above terms is immediately not obvious but if we multiply the previous term
with 3 and subtract the current term from it, we notice that we are off by a
power of 2.
3*1 - 1 =
2
3*1 - 7 =
-4
3*7 - 13 =
8
3*13 - 55 =
-16
...
After noticing the
above elegant relations, we obviously feel like generalizing the entire
sequence. We present our generalization of Fibonacci sequence in Scheme
code:
(define (gf-phi
multiple) (/ (+ 1 (sqrt (+ 1 (* 4 multiple)))) 2))
The above obtains the value of phi for various values like 1, 2, 6, ETC which we have discussed above.
The above obtains the value of phi for various values like 1, 2, 6, ETC which we have discussed above.
(define
(first-difference first second multiple) (- second (* first (gf-phi
multiple))))
The above obtains the difference between the first term and the second term if the second term does not equal phi times the first term. This is not a simple difference. We multiply the first term with phi and then, subtract from it the second term. (define (gf-next current index first second multiple) (+ (* (gf-phi multiple) current) (* (first-difference first second multiple) (power 1 (- 1 (gf-phi multiple)) (- index 1)))))
This is the final equation that gives all the answers that we need. For example, we start the ordinary Fibonacci equation with 5 and 7 instead of 1 and 1, we obtain: 5 7 12 19 31 ... In the above function, current stands for the current term in the sequence. For example, it can be 19. Index stands for the index of the term. In this case of 19, it is 4. First is 5 and second is 7. Multiple is 1. (gf-next 19 4 5 7 1) We get 31.0. Similarly, we can write: (gf-next 40 4 2 4 6) We get 136.0
The above obtains the difference between the first term and the second term if the second term does not equal phi times the first term. This is not a simple difference. We multiply the first term with phi and then, subtract from it the second term. (define (gf-next current index first second multiple) (+ (* (gf-phi multiple) current) (* (first-difference first second multiple) (power 1 (- 1 (gf-phi multiple)) (- index 1)))))
This is the final equation that gives all the answers that we need. For example, we start the ordinary Fibonacci equation with 5 and 7 instead of 1 and 1, we obtain: 5 7 12 19 31 ... In the above function, current stands for the current term in the sequence. For example, it can be 19. Index stands for the index of the term. In this case of 19, it is 4. First is 5 and second is 7. Multiple is 1. (gf-next 19 4 5 7 1) We get 31.0. Similarly, we can write: (gf-next 40 4 2 4 6) We get 136.0
