Generating functions demonstrated

Yes! Solved a problem ( well, just an exercise from Aigner's book, A course in Enumeration, which I particularly like ). Let me explain.

The problem was as stated as folows. Find $a_n$ such that
$$\sum_{k=0}^n {a_k * a_{n-k}} =1, \text{ for all } n$$.

In the case of a sequence of only two items this means that the following two statements must be true:
$a_1 * a_1 = 1$,
$a_1 * a_2 + a_2 * a_1 = 1$

We can simply see that the first two items of the sequence must be $(1,\frac{1}{2})$ since $1 * 1 = 1$, and $1 * \frac{1}{2} + \frac{1}{2} * 1 = 1$.

But we are looking for an infinite sequence! Would such a sequence at all exist? Well, it exists and there are probably several ways to find it. I used the theory of generating functions. As I explained earlier in my blog generating functions are formal power series representing infinite sequences.

Since the generating function of the sequence $(1,1,1 \cdots)$ is $\frac{1}{1-z}$, we know,if $g(z)$ is the generating function of the sequence we are looking for, that :
$${g(z)}^2 = \frac{1}{1-z} \Leftrightarrow $$
$${g(z)} = \sqrt{\frac{1}{1-z}} \Leftrightarrow $$
$$g(z) = (1-z)^{-\frac{1}{2}}.$$
But this is simply Newtons binomial formula, so the sequence we are looking for is: $$a(n) = C(\frac{2n-1}{2}, n)$$ with first five items:
$$(C(-\frac{1}{2},0), C(\frac{1}{2},1), C(\frac{3}{2},2), C(\frac{5}{2},3), C(\frac{7}{2},4), \cdots) = $$
$$(1,\frac{1}{2},\frac{3}{8},\frac{5}{16},\frac{35}{128}, \cdots)$$.

This is why I find generating functions beautiful and incredibly powerful.