Generating Functions Now we need to derive a generating function for the sequence (0,1,f1+f0,f2+f1,f3+f2,… One approach is to break this into a sum of three sequences for which we know generating functions and then apply the Addition rule (0. 0, 0,fo, .,6 0ff f2, 2F(a) 0.1+f0,f1+fo,f2+f1,f3+f2,…) c+F()+a F(ar) This sequence is almost identical to the right sides of the Fibonacci equations. The one blemish is that the second term is 1 fo instead of simply 1. However, this amounts to nothing, since fo=0 anyway witing down ail of the equations that define the Fibonacci numbers in one fell swoop. ta Now if we equate F()with the new function r+ar F(ar)+x F(r), then were implic F o+ f1 a+ f2 f3 x+ f2 x+xF(x)+x2F(x)=0+(1+f0)x+(f1+f0)x2+(f2+f1)x3+(f3+f2)x4+ olving for F(a) gives the generating function for the Fibonacci sequence (x) (x)+x2F(x) F(x)=1 Sure enough, this is the simple generating function we claimed at the outset 3.2 Finding a closed Form Why should one care about the generating function for a sequence There are several answers, but here is one: if we can find a generating function for a sequence, then we can often find a closed form for the n-th coefficient--which can be pretty useful! For example, a closed form for the coefficient of n in the power series for r/(1-x-c2)would be an explicit formula for the n-th Fibonacci number So our next task is to extract coefficients from a generating function. There are sev eral approaches. For a generating function that is a ratio of polynomials, we can use the method of partial fractions, which you learned in calculus. Just as the terms in a pa tial fractions expansion are easier to integrate, the coefficients of those terms are easy compute Let's try this approach with the generating function for Fibonacci numbers. First, we factor the denominator: (1-a1)(� � � � � � � Generating Functions 7 Now we need to derive a generating function for the sequence: �0, 1, f1 + f0, f2 + f1, f3 + f2, . . .� One approach is to break this into a sum of three sequences for which we know generating functions and then apply the Addition Rule: � 0, 1, 0, 0, 0, . . . � ←→ x � 0, f0, f1, f2, f3, . . . � ←→ xF(x) + � 0, 0, f0, f1, f2, . . . � ←→ x2F(x) 0, 1 + f0, f1 + f0, f2 + f1, f3 + f2, . . . � ←→ x + xF(x) + x2F(x) This sequence is almost identical to the right sides of the Fibonacci equations. The one blemish is that the second term is 1 + f0 instead of simply 1. However, this amounts to nothing, since f0 = 0 anyway. Now if we equate F(x) with the new function x+xF(x)+x2F(x), then we’re implicitly writing down all of the equations that define the Fibonacci numbers in one fell swoop: F(x) = f0 + f1 x + f2 x2 + f3 x3 + f4 x4 + . . . x + xF(x) + x2F(x) = 0 + (1 + f0) x + (f1 + f0) x2 + (f2 + f1) x3 + (f3 + f2) x4 + · · · Solving for F(x) gives the generating function for the Fibonacci sequence: F(x) = x + xF(x) + x 2 F(x) x ⇒ F(x) = 1 − x − x2 Sure enough, this is the simple generating function we claimed at the outset! 3.2 Finding a Closed Form Why should one care about the generating function for a sequence? There are several answers, but here is one: if we can find a generating function for a sequence, then we can often find a closed form for the n­th coefficient— which can be pretty useful! For example, a closed form for the coefficient of xn in the power series for x/(1 − x − x2) would be an explicit formula for the n­th Fibonacci number. So our next task is to extract coefficients from a generating function. There are sev￾eral approaches. For a generating function that is a ratio of polynomials, we can use the method of partial fractions, which you learned in calculus. Just as the terms in a par￾tial fractions expansion are easier to integrate, the coefficients of those terms are easy to compute. Let’s try this approach with the generating function for Fibonacci numbers. First, we factor the denominator: 1 − x − x 2 = (1 − α1x)(1 − α2x)