Recurrences and Generating Functions in Algorithms
Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik. The examples below are from these books (the mistakes and lack of clarity are mine).

Suppose that you're looking for the ways to make change with a given set of coins. For example, with common US denominations¹, the possible coins are $[1], [5], [10], [25], [100]$. To give ¢42 in change, one possibility is $[25][10][5][1][1]$; another possibility is $[10][10][10][10][1][1]$. We'll write $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$. More generally, we can write a generating function for all the ways to give change:
$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$
In more technical terms, $H$ is a term in the space of power series over the five variables $[100], [25], [10], [5], [1]$. Define the valuation of a monomial in this space by
$$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$
Then the ways to give $v$ cents in change are the number of monomials whose valuation is $v$. We can express $H$ in an incremental fashion, by first writing down the ways $P$ to give change in pennies only, then the ways $N$ to give 
change in pennies and nickels, and so on. ($I$ means no coin.)
$$\begin{gather*}
  P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\
  N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\
  D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\
  Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\
  H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\
\end{gather*}$$
If you want to count and not just enumerate the ways to give change, then there is a simple way to use the formal series we've obtained. Apply the homomorphism
$$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100} $$
The coefficient of $X^v$ in $S(C)$ is the number of ways to give $v$ cents in change.

A harder example: suppose that you want to study all the ways to tile rectangles with 2×1 dominoes. For example, there are two ways to tile a 2×2 rectangle, either with two horizontal dominoes or with two vertical dominoes. Counting the number of ways to tile a $2 \times n$ rectangle is fairly easy, but the $3 \times n$ case quickly becomes nonobvious. We can enumerate all the possible tilings of a horizontal band of height 3 by sticking dominoes together, which quickly yields repetitive patterns:
$$\begin{cases}
  U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\
  V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\
  \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\
\end{cases}$$
where the funny shapes represent elementary domino arrangements: $\mathsf{o}$ is no domino, $\mathsf{L}$ is a vertical domino on top of the left part of a horizontal domino, $\substack{\strut\\\mathsf{I}}$ is a vertical domino aligned with the bottom of the band of height 3, $\substack{\:-\\=}$ is a horizontal domino aligned with the top of the band plus two horizontal dominoes below it and one step to the right, etc. Here, multiplication represents horizontal concatenation and is not commutative, but there are equations between the elementary patterns that form variables in this power series. As before with the coins, we can substitute $X$ for every domino and get a generating series for the number of tilings of a $3 \times (2n/3)$ rectangle (i.e. the coefficient of $X^{3k}$ is the number of ways to tile a rectangle of area $6k$, which contains $3k$ dominoes and has the width $2k$). The series can also be used in more versatile ways; for example, by distinguishing vertical and horizontal dominoes, we can count the tilings with a given number of vertical and horizontal dominoes.

Again, read Concrete Mathematics for a less rushed³ presentation.

¹  I know my list is incomplete; assume a simplified US suitable for mathematical examples.² 
²  Also, if it comes up, assume spherical coins. 
³  And better typeset.