(41) Fibonacci & Lucas numbers
04-05-2020, 11:20 AM (This post was last modified: 04-13-2020 07:02 PM by SlideRule.)
Post: #1
 SlideRule Senior Member Posts: 1,312 Joined: Dec 2013
(41) Fibonacci & Lucas numbers
Pages 345 & 346 from Number Theory in Science and Communication, Second Enlarged Edition, © Springer·Verlag Berlin Heidelberg 1984 and 1986, ISBN 978-3-662-22246-1 (eBoook)

"B. A Calculator Program for Calculating Fibonacci and Lucas Numbers
To call the program, which is labeled "FN", from storage, press
GTO "FN"
To calculate, for example, the 12th Fibonacci number, F12, press
12
R/S .
After about 1 second one sees the answer:
144,
with a comma at the end. Pressing
R/S
again gives the 12th Lucas number, L12:
322 .
with a period at the end (to distinguish it from the Fibonacci number and to tell the user that the calculator is ready to accept the next index). The calculator is accurate up to F39 and L37.
Pressing the multiplication sign yields
F2n = Fn  ּLn = 46368 (for n = 12) .
This rule comes in handy to calculate Fn for large even n.
The odd-index Fn are calculated by
F2n+1 = gF2n = 75025 (for n = 12) ,
where g = 1.618 ... is the Golden ratio, stored in register 02.

Listing for "FN"

Comment                          Step     Code
initialize by calculat-
ing two constants              01        LBL "FN"
02        5
03        SQRT
04        STO 01
05        1
06        +
07        0.5
08        *
Golden Ratio                      09        STO 02
10        RDN
subroutine for calculat-       11        LBL 11
ing Fn and Ln                    12        RCL 02
13        x < > y
14        y^x
15        STO 03
16        RCL 01
17        /
18        0.5
19        +
20        INT
21        FIX 0
22        CF 28
display Fn                         23        STOP
24        RCL 03
25        0.5
26        +
27        INT
28        SF 28
display Ln                         29        STOP
ready to start over             30        GTO 11
31        END"

BEST!
SlideRule

corrected spelling errors
04-13-2020, 04:49 PM (This post was last modified: 04-16-2020 09:34 PM by Albert Chan.)
Post: #2
 Albert Chan Senior Member Posts: 1,552 Joined: Jul 2018
RE: (41) Fibonacci & Lucas numbers
Let g = (1+√5)/2 ≈ 1.618
Let h = 1-g ≈ -0.618 < 0

g^n ﻿=﻿ g F(n) + F(n-1)
h^n = h F(n) + F(n-1)

sum: L(n) = g^n + h^n = (g+h) F(n) + 2 F(n-1) = F(n) + 2 F(n-1)
difference: ﻿g^n - h^n = (g-h) F(n) = (2g-1) F(n) = √(5) F(n)

We can also get F(n) L(n) by curve fitting

XCas> g := (1+sqrt(5))/2
XCas> f(n) := c0*g^n + c1*(1-g)^n
XCas> solve([f(0),f(1)] = [0,1], [c0,c1]) ﻿ ﻿ ﻿ ﻿ → F(n) coeff = [1/√5, -1/√5]
XCas> solve([f(0),f(1)] = [2,1], [c0,c1]) ﻿ ﻿ ﻿ ﻿ → L(n) coeff = [1, 1]

As n gets big: F(n+1)/F(n) ≈ g, L(n)/F(n) ≈ 1 + 2/g = 1 + 2*(g^2-g)/g = 2g-1 = √(5)

For n≥3, F(n) = floor(g F(n-1) + .5)
For n≥3, L(n) = floor(√(5) F(n) + .5)
04-13-2020, 05:40 PM (This post was last modified: 04-13-2020 06:00 PM by Albert Chan.)
Post: #3
 Albert Chan Senior Member Posts: 1,552 Joined: Jul 2018
RE: (41) Fibonacci & Lucas numbers
Also from the book, Number Theory in Science and Communication, allowed complex numbers, we have:

Let $$\large z_1 = \cos^{-1}({-i \over 2})\quad\; → F_n = i^{n-1} {\sin (n z_1) \over \sin (z_1)} \quad\; → L_n = i^{n-1} {\cos (n z_1) \over \cos(z_1)} = 2\; i^n \cos (n z_1)$$

Or, with hyperbolics:

Let $$\large z_2 = \cosh^{-1}({-i \over 2})\quad → F_n = i^{n-1} {\sinh (n z_2) \over \sinh (z_2)} \quad → L_n = i^{n-1} {\cosh (n z_2) \over \cosh(z_2)} = 2\; i^n \cosh (n z_2)$$

Note: L(n) formula derive from identity L(n) = F(2n)/F(n), and sin(2 z) = 2 sin(z) cos(z)
Note: Hyperbolics formulas derived from z1 = i*z2, and identities sin(z) = sinh(i*z)/i, cos(z) = cosh(i*z)
04-16-2020, 07:19 PM (This post was last modified: 04-16-2020 07:46 PM by Albert Chan.)
Post: #4
 Albert Chan Senior Member Posts: 1,552 Joined: Jul 2018
RE: (41) Fibonacci & Lucas numbers
Starting from Binet's formula, where $$φ = {1+\sqrt5 \over 2}$$

$$\sqrt5 F_n = φ^n - (1-φ)^n = φ^n - (-1/φ)^n = φ^n - i^{2n} φ^{-n} = i^n \left(({φ \over i})^n - ({φ \over i})^{-n} \right)$$

$$\large F_n = {2 \over \sqrt5}\; i^n \sinh(n \ln({φ \over i}))$$

Let $$z_3 = \ln({φ \over i}) = \ln(φ) - {\pi \over 2} i$$

$$\large \cosh z_3 = {{φ \over i} + {i \over φ} \over 2} = {-i φ\; +\; i (φ-1) \over 2} = {-i\over2}$$

$$\large \sinh z_3 = ± \sqrt{ \cosh^2 z_3 - 1 } = ± \sqrt{{-5\over4}} = {-\sqrt5 i\over 2} = {\sqrt5 \over 2i}\quad$$ // principle branch

$$\large F_n = \left({2i \over \sqrt5}\right) i^{n-1} \sinh(n z_3) = i^{n-1} {\sinh(n z_3) \over \sinh(z_3)} \quad$$ // matching previous post
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)