Fibonacci Numbers and Binet's Formulausing Generating Functions

Fibonacci Numbers and Binet's Formula using Generating Functions/Innite Sums A sequence 1, 3, 5, 7, 9, 13, . . .) is a list of numbers that never ends (e.g. The Fibonacci Sequence is an exciting sequence of numbers we will talk about today. The rst few numbers are: f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 0 1 1 2 3 5 8 13 21 34 ... ... The rule that makes the Fibonacci Sequence is the next number is the sum of the previous two. This kind of rule is sometimes called a recurrence relation. Mathematically, this is written as: fn = fn−1 + fn−2 There is an explicit formula for the n-th Fibonacci number known as Binet's formula: 1 fn = √ 5 √ !n 1+ 5 1 −√ 2 5 √ !n 1− 5 2 In the rest of this note, we will explain how this works by using a really powerful idea called  generating functions which let us attack these problems. Generating functions involve using algebra to solve innite sums. Before we jump into Fibonacci, we will start with some warm up problems to get the hang of it. (Note that innite sums can be slippery...not all innite sequences can be summed. We won't worry about these technicalities here!) (Note also the solutions to the exercises are included on the next page) Exercise 0: 1+ Exercise 1: 1 + x + x2 + x3 + x4 + . . . = ? Exercise 2: 1 + 2x + 4x2 + 8x3 + 16x4 + . . . = ? Exercise 3: 1 + 2x + 3x2 + 4x3 + 5x4 + . . . = ? 1 2 + 1 4 + 1 8 + 1 16 + 1 32 + ... = ? 1 Generating Functions For any sequence of numbers, there is a x.) I mean an expression that depends on the sequence by Denition: xn , generating function associated with that sequence. (By a function, The rule for the generating function is to multiply each term of and nally do the innite sum of all these terms. This is written mathematically as: a0 , a1 , a2 , a3 , . . . The generating function for the sequence is the innite sum: S = a0 · x0 + a1 · x1 + a2 · x2 + a3 · x3 + . . . Here are some examples. We already did the work for these as exercises on the previous page! Example 1: The generating function for the sequence We must evaluate the innite sum is S= 1 1−x . S = 1 · x0 + 1 · x1 + 1 · x2 + 1 · x3 + . . . . − S= 1+ x+ x2 + x3 + . . . xS = x+ x2 + x3 + . . . ∴ (1 − x) S = 1+ 0+ ∴S= Example 2: 1, 1, 1, 1, 1 . . . 0+ We use the "shifting trick": 0 + ... 1 1−x The generating function for the sequence 1, 2, 4, 8, 16 . . . is S= 1 1−2x . S = 1 · x0 + 2 · x1 + 4 · x2 + 8 · x3 + . . . . 0 1 2 3 Notice that we can rewrite each term as a power of 2x, namely S = 1 · x + (2x) + (2x) + (2x) + . . .. Now we can use the same shifting trick as before (Alternatively, you can "plug in 2x into Example 1): We must evaluate the innite sum S= − 1+ (2x)2 + . . . 2x+ (2x)2 + . . . 0+ 0 + ... 2xS = ∴ (1 − 2x) S = 1+ 1 1−2x ∴S= Example 3: (2x)+ The generating function for the sequence We must evaluate the innite sum 1, 2, 3, 4, 5, 6 . . . is S= S = 1 · x0 + 2 · x1 + 3 · x2 + 4 · x3 + . . . . 1 (1−x)2 . We can use the same shifting trick to reduce this to the sum we already computed in example 1: S= − 1+ xS = ∴ (1 − x) S = = 1+ 2x+ 3x2 + 4x3 + . . . x+ 2x2 + 3x3 + . . . x+ x2 + x3 + . . . 1 1−x from Example 1 ∴S= Fact 1: 1 (1−x)2 The generating function for the Fibonacci sequence We must evaluate the innite sum is S= S = 0 · x0 + 1 · x1 + 1 · x2 + 2 · x3 + 3 · x4 . . . . relation for the Fibonacci numbers involves the last two 0+ x+ x2 + 2x3 + 3x4 + 5x5 + . . . xS = 0+ x2 + x3 + 2x4 + 3x5 + . . . − x2 S =
∴ 1 − x − x2 S = 0+ x+ 0+ x3 + x4 + 2x5 + . . . 0+ 0+ x ∴S= (1 − x − x2 ) 0+ 0 + ... 0's x 1−x−x2 . Since the recurrence numbers, we must use a "double" shifting trick: S= − The reason all the 0, 1, 1, 2, 3, 5, 8 . . . appear is from the recurrence relation for the Fibonacci numbers; in other words the fact that the next Fibonacci number is the sum of the previous two. 2 The Golden Ratio ϕ Dene two numbers and β to be the roots of the quadratic equation x2 − x − 1. (This quadratic equation appeared "in reverse" in the denominator for the generating function of the Fibonacci numbers). By the quadratic equation, these are: √ 1+ 5 ≈ 1.6180339887 . . . ϕ= 2 √ 1− 5 β= ≈ −0.6180339887 . . . 2 The number ϕ is called the page for more info!). Both ϕ Golden Ratio and has a number of exciting properties (go see the Wikipedia and β are intimately related to the Fibonacci sequence because they appear in the generating function! Fact 2: 1 − x − x2 = (1 − ϕx)(1 − βx) You can check this fact by expanding it out using "FOIL" and the fact that ϕβ = −1 and ϕ + β = 1. Try it here! Fact 3: Let fn be the n-th Fibonacci number. Then we have the explicit formula: fn = √1 5 (ϕn − β n ) The trick we use to get this result is to rewrite the generating function for the Fibonacci numbers x (1−x−x2 ) we found in Fact 1 using the factorization By some algebraic manipulations, (This is called the S= 1 − x − x2 = (1 − ϕx)(1 − βx) partial fractions trick!) we found in Fact 2. we nd that: x 1 1 1 1 =√ −√ 1 − x − x2 5 1 − ϕx 5 1 − βx Now we recognize that 1 1 1−ϕx and 1−βx look a lot like the answer from Example 2. These are innite sums! 1 = 1 + βx + β 2 x2 + β 3 x3 + . . . 1 − βx 1 = 1 + ϕx + ϕ2 x2 + ϕ3 x3 + . . . 1 − ϕx Putting this all together gives: = = = = f0 + f1 x + f2 x2 + f3 x3 + . . . x 1 − x − x2 1 1 1 1 √ −√ 5 1 − ϕx 5 1 − βx

1 1 √ 1 + ϕx + ϕ2 x2 + ϕ3 x3 + . . . − √ 1 + βx + β 2 x2 + β 3 x3 + . . . 5 5

1 1 1 2 2 0 + √ (ϕ − β) x + √ ϕ − β x + √ ϕ3 − β 3 x3 + . . . 5 5 5 Since these two "polynomials" are equal for every value of o the coecients of the power xn x, each term must individual by equal. gives the nal result, 1 1 fn = √ (ϕn − β n ) = √ 5 5 √ !n 1+ 5 1 −√ 2 5 . This is Binet's formula! 3 √ !n 1− 5 2 Reading Converting Miles to Kilometers Factoid 1: Fibonacci numbers can be used to convert miles to kilometers by: fn km ≈ fn−1 mi The secret of this factoid is an amazing coincidence between the numerical value of kilometers in a mile, and the fact that |β| < 1. ϕ and the number of Firstly, notice that: ϕ = 1.6180 . . . 1mi = 1.6093 . . . 1km Because these two values are close, the approximation Now notice that since β < 1, that βn is really small as n 1 mi ≈ ϕ km is pretty good (to about β n ≈ 0. So we have some gets larger; 1%). more approximations: fn fn−1 ∴ fn Along with when n 1mi ≈ ϕkm, 1 1 √ (ϕn − β n ) ≈ √ ϕn 5 5
1 1 n−1 n−1 = √ ϕ −β ≈ √ ϕn−1 5 5 ≈ ϕfn−1 = fn−1 km ≈ fn mi. This works best if n is not-too-small, because β n ≈ 0 becomes more accurate. n = 5 is already quite a good couple listed for you, starting at n = 5: this means that is large, our approximation that approximation (β 4 ≈ 0.0002). The rst 3 mi ≈ 5 km 5 mi ≈ 8 km 8 mi ≈ 13 km If you want to covert numbers not on this list, you can bootstrap from the above approximations. example, starting from 5mi ≈ 8km, For you can do: 100mi = 20 · 5mi ≈ 20 · 8km = 160km If you found this interesting... Here are some great websites that you can check out where you can get more! Wikipedia links: • Fibonacci number • Golden ratio • Recurrence relation • Generating function Other links: • Doodling in Math: Spirals, Fibonacci, and Being a Plant [1 of 3] by Vi Hart. http://www.khanacademy.org/math/vi-hart/v/doodling-in-mathspiralsbonacciand-being-a-plant 1-of-3 • Exercise - Write a Fibonacci Function by Salman Khan (has a computer science avor) https://www.youtube.com/watch?v=Bdbc1ZC-vhw 4