(41) Fibonacci & Lucas numbers

[SlideRule]

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

[Albert Chan]

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)

[Albert Chan]

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 z₁ = i*z₂, and identities sin(z) = sinh(i*z)/i, cos(z) = cosh(i*z)

[Albert Chan]

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