Generating Functions
A quick review from their introduction in chapter 5, a generating function is a sequence of coefficients to finite and infinite polynomials. In calculus, they let you approximate any function with enough terms. Here, we'll relate them to recurrences.
Sequence Notation: A condensed version of the polynomial
e.g.
$\sum_{k=0}^{\infty} x^k = <1,1,1,1,\dotso>$
Generating Function: The function whose coefficients of the expansion into a power series (Maclaurin series) are a given sequence.
$f(x) = \frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + \dotso$
Because these are like polynomials, we can do some basic operations on them, such as differentiation, integration, and the 4 fundamental arithmetic operations. Here are some examples with $g(x) = <1,2,3,4,5,6,\dotso>$
shifting the sequence via multiplication
$g(x)*x = \sum_{k=1}^n x^k = <0,1,2,3,4,5,\dotso>$
differentiating the sequence
$g(x) ' = \sum_{k=1}^n k x^{k-1} = <2,2\cdot3,3\cdot4,4\cdot5,\dotso> = <2,6,12,20,\dotso>$
$\int g(x) dx= \sum_{k=1}^n x^k = <0,1,2/2,3/3,4/4,5/5,\dotso>$
when we integrate this sequence, we get $\int g(x) dx = f(x) = \frac{x}{1-x}$, which means that $g(x) = f(x)' = \frac{1}{(1-x)^2}$
Finally, the most important operation:
$g(x) = \frac{1}{(1-x)^2} = <1,2,3,4,5,6,\dotso>$
$f(x) = \frac{1}{(1-x)} = <1,1,1,1,1,1, \dotso>$
$f(x) \cdot g(x) = (1 + x + 2x^2 + 3x^3 + 4x^4 + \dotso) \cdot (1 + x + x^2 + x^3 + x^4 + \dotso) = \\ 1 + (1 + 1) x + (1 + 1 + 2) x^2 + (3 + 2 + 1 + 1) x^3 + \dotso$
If we notate the coefficients of f(x) as $<a_0,a_1,a_2,\dotso>$ and g(x) as $<b_0,b_1,b_2,b_3,\dotso>$, then we notice a pattern:
$f(x) \cdot g(x) = \sum_{n \geq 0} \sum_{j=0}^n(a_jb_{n-j})x^n$
In other words, the product of these two generating functions, is the generating function that is convolution of their series!
Fibonacci Recurrence Closed Form
To illustrate the connection to recurrences, let's start by trying to find the generating function of our favorite sequence : the Fibonacci numbers. Although you probably didn't forget from last time, for completeness let's write its definition.$$
F_n = F_{n-1} + F_{n-2}, \\
F_0 = 0, \ \ \ \ F_1 = 1
$$
and the first few numbers are 0, 1, 1, 2, 3, 5, 8, 13, etc... Now, what we want is the generating function that represents this sequence. In other words, the function:
$$g(x) = F_0 x^0 + F_1x + F_2x^2 + F_3x^3 + F_4x^4 + \dotso = \\ x + x^2 + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + 21x^7 + \dotso $$
If we manipulate our recurrence, i.e.
$$
x \cdot g(x) = F_0 x^1 + F_1x^2 + F_2x^3 + F_3x^4 + F_4x^5 + \dotso \\
x^2 \cdot g(x) = F_0 x^2 + F_1x^3 + F_2x^4 + F_3x^5 + F_4x^6 + \dotso
$$
We can relate this to our original definition
$$g(x) - xg(x) - x^2g(x) = \\ F_0 x^0 +(F_1 - F_0)x + (F_2 - F_0 - F_1)x^2 + (F_3 - F_2 - F_1)x^3 + (F_4 - F_3 - F_2)x^4 + \dotso = \\ F_0 x^0 +(F_1 - F_0)x = x$$
Thus we can rewrite this as
$g(x) - xg(x) - x^2g(x) = x$
and find the generating function
$g(x) = \frac{x}{1-x-x^2}$
So, recall that the n'th coefficient of this series gives us the n'th fibonacci number. In order to isolate that, we need to break down our expression into partial fractions. In simple terms, that means we find some $\frac{A}{1-\alpha x} + \frac{B}{1-\beta x} = \frac{x}{1-x-x^2}$. Since these two simpler fractions give us two separate power series $A\sum_{k\geq0}(\alpha x)^k$ and $B\sum_{k\geq0}(\beta x)^k$, we would be able to compute the n'th fibonacci number by summing the two coefficients of the k'th terms $F_n = A (\alpha)^n + B (\beta)^n$
You can do the procedure by creating a common denominator on the right side and then solving for A, B, but our decomposition is $ \frac{x}{1-x-x^2} = \frac{1}{\sqrt{5} (1 - \frac{1+\sqrt{5}}{2}x)} + \frac{-1}{\sqrt{5}(1- \frac{1-\sqrt{5}}{2}x)}$
And thus we get our closed form
$$F_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$$
Note that $\frac{1+\sqrt{5}}{2}$ is often called $\phi$(phi) and is famous because of the golden ratio.
Anyway, our solution sort of hints at a general procedure that we'll cover in a bit. Let's look at another example first.
Domino Theory
Moving onto a more abstract problem, say we want to find the number of ways we tile 2x1 tiles on a 2xN surface (the author calls them dominoes, but I don't think many people will know of the non-pizza variety in the future).
Imagine that we can define this sequence using these symbols
The core of this trick is noticing how you can define the sequence in terms of itself.
Now that we've noticed this, we no longer need to use these symbols. In terms of generating functions, our N'th coefficient would be the number of ways to construct $2 \cdot N$ tiles-strips. A tile with m components in our enumeration is just one $z^m$ term. We can rewrite our symbolic statement as
$G(z) = 1\cdot z^0 + z G(z) + z^2 G(z)$
and solve for our generating functions
$$ G(z) = \frac{1}{1-z-z^2} $$
which is almost the same as our Fibonacci generating function, but divided by z. Now think about what dividing by z does to Fibonacci series. It shifts it by one!
If we drop the symbols and enumerate the series for small N, we see that the way to construct a 2xN tileset is as follows
N 0 1 2 3 4 5
-----------------------------
2xN 1 1 2 3 5 8
Because of this, and the shift from the original fibonacci generating function, we see that this is just the Fibonacci sequence, but shifted by one!
Considering the 3xN Case
Using the same basic components, we now want to know the number of ways we can construct a 3xN tileset. Let's use our crazy tile notation and look for a pattern
Now, the first observation you may notice, is that we can only make 3xN tilesets when N is an even number. The reason is pretty obvious if you think about it: our base units have areas of two, therefore our 3xN region is only possible to construct with them if its area is divisible by two.
Now, the next observation is that there's a special way we can construct our infinite sequence of 3xN tilesets sort-of in terms of itself.
we can do the same operations for the opposite symbol, and we can rewrite our original recurrence as
where $\alpha$ is our upper L, $\beta$ is our lower L and $gamma$ is three horizontal bars. Our observation of how to construct $V$ in terms of itself gives us the relation $V = a_u \cdot G + b_u \cdot V$ and applying the same exact logic to our lower L gives us $\wedge = a_d G + b_d \wedge$ these three equations for three unknowns let us solve for $G$.
Solving Recurrences
At long last, we learn how to solve recurrences. Our procedure of using generating functions breaks down into 4 steps given a sequence $<g_n>$:- Write down a single equation expressing $g_n$ in terms of the other elements in a sequence(i.e. find a recurrence).
- Multiply both sides of this equation by $z^n$ and sum over all $n$. You'll have $\sum_n g_n z^n$ on the left side, which is our generating function $G(z)$, so we can notate it as such.
- Solve the equation for $G(z)$ by factoring it out of the right-hand side.
- Expand $G(z)$ into a power series, the coefficient to $z^n$ will be $g_n$. You can use many methods to get the closed form here, but you essentially have to decompose $G(z)$ into known power series.
Fibonacci Take 2
Just to hammer in how much more efficient this method is, let's revisit our first problem
$$
F_n = F_{n-1} + F_{n-2}, \ \
F_0 = 0, \ \ \ \ F_1 = 1
$$
so let's take step 1, which is practically done for us, but define it formally
$$ \begin{equation}
g_n=
\begin{cases}
0, & \text{if}\ a=1 \\
1, & \text{if}\ a=1 \\
g_{n-1}+g_{n-2}, & \text{otherwise}
\end{cases}
\end{equation}
$$
thus we can write
$g_n = g_{n-1} + g_{n-2}$
however, as per the single-equation requirement, we now need our formula to hold for all real numbers, and this construction specifically does not hold when n=1! So we can fix it by adding a
condition
$g_n = g_{n-1} + g_{n-2} + [n=1]$
Ok, so now that it holds, we apply step 2
$$G(z) = \sum_{n}g_nz^n = \sum_{n}g_{n-1}z^n + \sum_{n}g_{n-2}z^n + \sum_{n}[n=1]z^n \\
= \sum_{n}g_nz^n = \sum_{n}g_{n}z^{n+1} + \sum_{n}g_nz^{n+2} + z \\
= zG(z) + z^2G(z) + z$$
Wow, now step 3
$$G(z) = \frac{z}{1-z-z^2}$$
and step 4 we have already done above, but wow! Just by being technical with our problem specification, we can apply our algorithm and get results almost automatically!
A Warm-up
A new example with this technique
$$g_0 = g_1 = 1 \\
g_n = g_{n-1} + 2g_{n-2} + (-1)^n,\ \ \text{for} \ n \geq 2$$
As per step 1, we write out equation, with the fix to make it hold for $n<2$ cases
$$g_n = g_{n-1} + 2g_{n-2} + (-1)^n,\ \ \text{for} \ n \geq 2 + (-1)^n[n\geq0] + [n=1]$$
Sweet, now let's apply step 2
$$G(z) = \sum_{n} g_n z^n = \sum_{n}g_{n-1} + 2sum_n g_{n-2} z^n + \sum_{n} (-1)^nz^n[n \geq 0] + \sum_{n}z^n[n=1] = \\ = zG(z) + 2z^2 G(z) + \frac{1}{1+z} + z$$
We're nicely set up for step 3
$$G(z) = \frac{1+z+z^2}{(1-2z)(1+z)^2}$$
And now for step 4, we need to find an expansion using the general expansion theorem, which since our roots are 2, and -1 repeating, we can find that $g_n = \frac{7}{9}2^n + (\frac{1}{3}n + 2/9)(-1)^n$
Exponential Generating Functions
If a generating function is too hard to work with, you might consider working with its exponential generating function counterpart.$$\hat{G}(z) = \sum_{n \geq 0} g_n \frac{z^n}{n!}$$
The exponential generating function (i.e. egf because $e^z = <1,1,1,\dotso>$) has slightly different properties when differentiating and multiplying that provide additional tools to our old method.
If we multiply an egf by z, we get $\sum_{n \geq 0} g_n \frac{z^{n+1}}{n!} = \sum_{n \geq 0} g_{n-1} \frac{nz^{n}}{n!}$
Differentiation:
$\hat{G}(z)' = \sum_{n \geq 0} ng_n \frac{nz^{n-1}}{n!} = \sum_{n \geq 0} g_{n+1} \frac{z^{n}}{n!}$
which is a clean left-shift!
Integration:
$\int_0^z{G}(z) dt = \sum_{n \geq 0} ng_n \frac{z^{n+1}}{(n+1)!} = \sum_{n \geq 0} g_{n-1} \frac{z^{n}}{n!}$
which gets us a right-shift, but most importantly if we try multiplying some $\hat{F}(z) \cdot \hat{G}(z) = \hat{H}(z)$ , then we get
$h_n = \sum_k {n \choose k}f_k g_{n-k}$
Dirichlet Generating Functions
We introduce this final, more academic class of generating functions called Dirichlet generating functions, named after a rather famous mathematician. It's a generating function whose sequence is of the form:$$\tilde{G}(z) = \sum_{n \geq 1} \frac{g_n}{n^z}$$
Negative powers! Powers in the denominator (the same power, that is) !
Remember our zeta function? Well
$$\sum_{n \geq 1} \frac{1}{n^z} = \zeta(z)$$
The convolution of two dirichlet generating functions has a special property.
$$\tilde{F}(z) \tilde{G}(z) = \sum_{l,m \geq 1} \frac{f_l g_m}{l^z m^z} = \sum_{l,m \geq 1}\frac{1}{n^z} \sum_{l,m \geq 1} f_l g_m [l \cdot m = n]$$
which, if we use notate $\tilde{F}(z) \tilde{G}(z) = \tilde{H}(z)$ resolves to
$$h_n = \sum_{d \backslash n} f_d g_{n/d}$$
Anyway, when a sequence is defined with some multiplicative recurrence, remember to look up dirichlet generating functions.
Conclusion
This concludes a cursory glance at generating functions. I highly suggest trying some problems from the book on your own (you'll make heavy use of table 335). I might revisit them again when generating solutions to programming challenges, but they provide a crucial general way of looking at series and recurrences that act as the peak of this book and course.
This also concludes our series of Discrete mathematics coverage. I started this because my undergrad discrete math class didn't have the rigorous level that I had always wanted. Rather, it's practically a necessity to treat it rigorously, since a quick glance of conceptual topics without the deep connections that we've drawn between chapters is too easy to forget. Hopefully some of you (2 people?) will have found this useful for your own studies.
Though we close this topic, we open a new one. Keep watching my posts as I start blogging about action-packed, tantilizing software development projects for a couple months in between this and the next step of keikaku!
This also concludes our series of Discrete mathematics coverage. I started this because my undergrad discrete math class didn't have the rigorous level that I had always wanted. Rather, it's practically a necessity to treat it rigorously, since a quick glance of conceptual topics without the deep connections that we've drawn between chapters is too easy to forget. Hopefully some of you (2 people?) will have found this useful for your own studies.
Though we close this topic, we open a new one. Keep watching my posts as I start blogging about action-packed, tantilizing software development projects for a couple months in between this and the next step of keikaku!
No comments :
Post a Comment