erating Function 3 The Fibonacci Sequence Sometimes we can find nice generating functions for more complic example, here is a generating function for the Fibonacci numbers Cated sequences. For (0,1,1,2,3,5,8,13,21, The Fibonacci numbers are a fairly nasty bunch, but the generating function is simple Were going to derive this generating function and then use it to find a closed form for the n-Fibonacci number Of course, we already have a closed form for Fibonacci numbers obtained from the cookbook procedure for solving linear recurrences. But there are a couple reasons to cover the same ground again. First, we'll gain some insight into why the cookbook method for linear recurrences works. And, second, the techniques well use are applicable to a large class of recurrence equations, including some that we have no other way to tackle 3. inding a Generating Function Let' s begin by recalling the definition of the Fibonacci numbers fo f1=1 fn=fn-1+fr (forn≥2) We can expand the final clause into an infinite sequence of equations Thus the fibonacci numbers are defined by f1 + fo f2+f1 f3+f2 Now the overall plan is to define a function F(a) that generates the sequence on the left side of the equality symbols, which are the Fibonacci numbers. Then we derive a function that generates the sequence on the right side. Finally, we equate the two and solve for F(. Let's try this Fi F(ar)=fo+fir+ f2.2+f3 r+f46 Generating Functions 3 The Fibonacci Sequence Sometimes we can find nice generating functions for more complicated sequences. For example, here is a generating function for the Fibonacci numbers: x �0, 1, 1, 2, 3, 5, 8, 13, 21, . . .� ←→ 1 − x − x2 The Fibonacci numbers are a fairly nasty bunch, but the generating function is simple! We’re going to derive this generating function and then use it to find a closed form for the n­Fibonacci number. Of course, we already have a closed form for Fibonacci numbers, obtained from the cookbook procedure for solving linear recurrences. But there are a couple reasons to cover the same ground again. First, we’ll gain some insight into why the cookbook method for linear recurrences works. And, second, the techniques we’ll use are applicable to a large class of recurrence equations, including some that we have no other way to tackle. 3.1 Finding a Generating Function Let’s begin by recalling the definition of the Fibonacci numbers: f0 = 0 f1 = 1 fn = fn−1 + fn−2 (for n ≥ 2) We can expand the final clause into an infinite sequence of equations. Thus, the Fibonacci numbers are defined by: f0 =0 f1 =1 f2 =f1 + f0 f3 =f2 + f1 f4 =f3 + f2 . . . Now the overall plan is to define a function F(x) that generates the sequence on the left side of the equality symbols, which are the Fibonacci numbers. Then we derive a function that generates the sequence on the right side. Finally, we equate the two and solve for F(x). Let’s try this. First, we define: 3 + f4x 4 F(x) = f0 + f1x + f2x 2 + f3x + · · ·