As of May 4 2007 the scripts will autodetect your timezone settings. Nothing here has to be changed, but there are a few things

Please follow this blog

Search this blog

Sunday, May 30, 2010

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.

No comments:

Post a Comment

Popular Posts

Welcome to The Bridge

Mathematics: is it the fabric of MEST?
This is my voyage
My continuous mission
To uncover hidden structures
To create new theorems and proofs
To boldly go where no man has gone before

(Raumpatrouille – Die phantastischen Abenteuer des Raumschiffes Orion, colloquially aka Raumpatrouille Orion was the first German science fiction television series. Its seven episodes were broadcast by ARD beginning September 17, 1966. The series has since acquired cult status in Germany. Broadcast six years before Star Trek first aired in West Germany (in 1972), it became a huge success.)