ABSTRACT
In this chapter we will devote our efforts to introducing and building up experience with using generating functions. It would first be useful, however, to show why any such experience is necessary. A relevant question the reader may ask at the conclusion of Chapter 1 is “Why is another approach, such as generating functions, necessary to solve difference equations?” In Chapter 1, some useful tools in identifying solutions to difference equations were demonstrated. One of these tools was to solve the equations one at a time, starting with k=0 and then working up through the sequence, using the solution for (k−1)st difference equation to obtain the solution for the kth equation. This is a very natural approach, as it is very helpful in many circumstances. The other approach is to try to guess the difference equation solution and to prove that answer for the entire difference equation family. As attractive as these approaches are, their limitations become clear when one considers a second-order nonhomogenous family of difference equations, e.g.,
yk+2=3yk+1+2yk+7 (2.1)
for k=0, 1, 2,…, ∞; y0, y1 are known constants. If we try to solve this family of difference equations iteratively, the process begins as follows. For k=0
y2=3y1+2y0+7 (2.2)
Proceeding to the next equation (k=1) y3=3y2+2y1+7=3(3y1+2y0+7)+2y1+7 =9y1+6y0+21+2y1+7 =11y1+6y0+28
(2.3)
The third equation yields y4=3y3+2y2+7=3(11y1+6y0+28)+2(3y1+2y0+7)+7 y4=33y1+18y0+84+6y1+4y0+14+7 =39y1+22y0+105
(2.4)
So, after solving the first three equations, y2=3y1+2y0+7 y3=11y1+6y0+28 (2.5)
y4=39y1+22y0+105
Only an algebraic genius would be able to see a pattern in the solutions of y2, y3, and y4 that would help to identify the values for each of y6, y7, and y8. The absence of this intuition is keenly felt here. Since the general solution to the family of difference equations as expressed in equation (2.1) cannot be intuited, neither of the methods discussed in Chapter 1 will be very helpful. It is because of these difficulties that arise from a very simple difference equation family that we turn to generating functions as a useful tool.
