Editing Generating function (section)

====Example: Generating function for the Catalan numbers====

An example where convolutions of generating functions are useful allows us to solve for a specific closed-form function representing the ordinary generating function for the [[Catalan numbers]], {{math|''C<sub>n</sub>''}}. In particular, this sequence has the combinatorial interpretation as being the number of ways to insert parentheses into the product {{math|''x''<sub>0</sub> · ''x''<sub>1</sub> ·⋯· ''x<sub>n</sub>''}} so that the order of multiplication is completely specified. For example, {{math|''C''<sub>2</sub> {{=}} 2}} which corresponds to the two expressions {{math|''x''<sub>0</sub> · (''x''<sub>1</sub> · ''x''<sub>2</sub>)}} and {{math|(''x''<sub>0</sub> · ''x''<sub>1</sub>) · ''x''<sub>2</sub>}}. It follows that the sequence satisfies a recurrence relation given by
<math display="block">C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} + \delta_{n,0} = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0 + \delta_{n,0}\,,\quad n \geq 0\,, </math>
and so has a corresponding convolved generating function, {{math|''C''(''z'')}}, satisfying
<math display="block">C(z) = z \cdot C(z)^2 + 1\,.</math>

Since {{math|''C''(0) {{=}} 1 ≠ ∞}}, we then arrive at a formula for this generating function given by
<math display="block">C(z) = \frac{1-\sqrt{1-4z}}{2z} = \sum_{n = 0}^\infty \frac{1}{n+1}\binom{2n}{n} z^n\,.</math>

Note that the first equation implicitly defining {{math|''C''(''z'')}} above implies that
<math display="block">C(z) = \frac{1}{1-z \cdot C(z)} \,, </math>
which then leads to another "simple" (of form) continued fraction expansion of this generating function.