134 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS
This identity can of course be proven in other ways (and you should know some of
them; if not, consult Section 6.2), but notice that our method is both easy and easy togeneralize. If we let x = -1, we get a completely new identity,
These two examples of plugging in a value to get an identity are typical of the
"local +-+ global" point of view. Globally, the generating function is just the simplefunction (1 + x)n. We can plug in any values that we want. But each time we plug in
a value, we get a new statement involving the coefficients (�) (the local information).
The key is to move the focus back and forth between the function and its coefficients,
to get useful information.Example 4.3.3 Plugging in values is just one of the global things we can do. Let's try
differentiation! If we differentiate both sides of (2), we getNow, if we plug in x = 1, we get the interesting identity
Recurrence Relations
So far, we have not used the simple fact mentioned on page 13 2, that xn xn = xn+m.
Let us do so now, by using generating functions to analyze recurrence relations (see
Section 6.4 for examples).Example 4.3.4 Define the sequence (an) by ao = 1 and an = 3an-l + 2 for n = 1,2, ....
Find a simple formula for an.
Solution: There are several ways to tackle this problem; indeed, the simplest
approach-one that any problem solver should try first-is to work out the first few
terms and guess. The first few terms are (verify!)1,5, 17,53, 161 ,4 85 , ... ,which may lead an inspired guesser (who knows her powers of 3) to conjecture that
an = 2. 3 n -1, and this is easy to prove by induction.
Let's look at an alternate solution, using generating functions. It is much less
efficient for this particular problem than the "guess and check" method above, but it
can be applied reliably in many situations where inspired guessing won't help. Let