daily pastebin goal
90%
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
Top