• API
• FAQ
• Tools
• Archive
daily pastebin goal
88%
SHARE
TWEET

Untitled

a guest Jan 19th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. The Fibonacci sequence is a driven by the second order linear difference equation
2.
3. Fn+2 = Fn+1 + Fn, with boundary conditions F1 = 1, F2 = 1,
4.
5. and thus can be solved exactly. As we know from practice that Fn is roughly exponential, we try Fn = Aa^n for A and a constants. This gives the quadratic
6.
7. a^2 = a + 1, which happens to be the equation for the golden ratio Φ, and its inverse which I'll denote Φ'
8. (i.e. Φ' = 1/Φ, Φ' = Φ - 1)
9.
10. As the equation is second order then it is a linear combination of these two solutions and the boundary conditions define the constants involved, i.e.
11.
12. Fn = AΦ^n  + BΦ'^n
13.
14. F0 = 0 (easy if you follow backwards) so A + B = 0
15. F1 = 1 . Using Φ = (1 + r)/2  and Φ' = (1 - r)/2  where r is the positive square root of 5, you can find
16.
17. A - B = 2/r  yielding A = 1/r, B = -1/r
18.
19. So Fn = (Φ^n /r) - (Φ'^n /r) = (Φ^n - Φ'^n)/r  for all n.
20.
21. As can be seen, the even terms are when n is a multiple of 3, so using this formula add F3 + F6 + ... until you get a term greater than one million. Thus a program for this could be only a handful of lines long. A slightly further simplification would be to work out Φ^3 and Φ'^3, call them b and b' respectively. Then
22.
23. F3k = (b^k - b'^k)/r  for k = 1,2,3...
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top