NOTE: This transcription was contributed by Martin P.M. van der Burgt, who has devised a process for producing transcripts automatically. Although its markup is incomplete, we believe it serves a useful purpose by virtue of its searchability and its accessibility to text-reading software. It will be replaced by a fully marked-up version when time permits. —HR
In honour of Fibonacci.
Studying an artificial intelligence approach to programming the other day —I read the most weird documents!— I was reminded of the Fibonacci sequence. given by
Fi = 0 , F2 = 1 , | |
F_{n} = F_{n-1} + F_{n-2} (-inf < n < +inf) | |
R: | x = F_{N} |
y, x, i := 0, 1, 2 {Y = F_{i-1} and x = F_{i} and 2 ≤ i ≤ N}; | (1) | |
do i ≠ N → y, x, i := x, x + y, i + l .od {R} |
Yesterday evening I was wondering whether I could reconstruct the logarithmic scheme for the Fibonacci sequence, and whether similar schemes existed for higher order recurrence relations (for a k ≥ 2 ):
F1 = F2 = ... = F_{k-1} = 0 , F_{k} = 1 | ||
F_{n} = F_{n-1} + ... + F_{n-k} (-inf < n < +inf) | (2) |
Eventually I found a way of deriving these schemes. For k = 2 , the normal Fibonacci numbers, the method leads to the well-known formulae
F_{2j} = f_{j}^{2} + F_{j+1}^{2} | |
F_{2j+1} = (2F_{j} + F_{j+1}) * F_{j+1} or F_{2j-1} = (2f_{j+1} - F_{j}) * F_{j} . |
Because for k = 3 we have F_{1} = F_{2} = 0 and F_{3} = l we may write
F_{n} = F_{3} * F_{n} + (F_{2} + F_{1})* F_{n-1} + F_{2} * F_{n-2} | (3) |
F_{n} = F_{i+3}* F_{n-i} + (F_{i+2} + F_{i+1})* F_{n-i-1}+ F_{i+2}* F_{n-i-2} | (4) |
1) substituting F_{n-i-1} + F_{n-i-2} + F_{n-i-3} for F_{n-i }
2) combining after rearrangement F_{i+3} + F_{i+2} + F_{i+1} for F_{i+4} .
(The proof for negative values of i is done by performing the induction step the other way round.) Substituting in (4) n = 2j and i = j-l we get
F_{2j} = F_{j}^{2} * F_{j+1} + (F_{j+1} + F_{j})* F_{j} + F_{j+1}* F_{j-1} |
F_{2j} = F_{j}^{2} + (2F_{j+2} - F_{j+1})* F_{j+1} | (5) |
F_{2j+l} = F_{j+2} + (F_{j+1} + F_{j})* F_{j+1} + F_{j+1} * F_{j} | ||
= (2F_{j} + F_{j+1}) * F_{j+1} + F_{j+2}^{2} | (6) |
Note. For k = 4 the analogue to (4) is F_{n} = F_{i+4} * F_{n-i} + (F_{i+3} + F_{i+2} + F_{i+1})* F_{n-i-1} + (F_{i+3} + F_{i+2})* F_{n-i-2} + F_{i+3} * F_{n-i-3} · (End of note.)
.
Plataanstraat 5 | prof.dr.Edsger W.Dijkstra |
5671 AL Nuenen | Burroughs Research Fellow |
The Netherlands |
Transcribed by Martin P.M. van der Burgt
Last revision