RichardKelley/gist:84994478e23a0775999be202195200fb

## gistfile1.txt
% A Simple LaTeX Example
% Author: Richard C Kelley

% This is a comment. A comment begins with a '%' and extends to the
% end of the line.

% We always start our LaTeX documents by specifying the document class
% we want to use. There are several document classes available that
% you could use if you wanted - article, book, report, letter,
% etc. For many purposes, though, all you need is the article
% class. You specify the document class with the following command:
\documentclass{article}

% Once we've specified the document class, we will probably want to
% include some packages. A package extends the basic set of commands
% and symbols that comes with LaTeX, and there are a few that are
% almost always useful. Those are the ones we include here:

% The first two packages listed below are from the American
% Mathematical Society, and include symbols and formatting options
% that make it much easier to typeset mathematics. The last package,
% verbatim, gives us an enviroment like <pre> in HTML, and is useful
% for typesetting computer code.
\usepackage{amsmath,amssymb,verbatim}

% If we want, we can have multiple \usepackage commands in our input
% file. The default margins in LaTeX are pretty big, so I like to make
% them smaller using this command. Here I set all the margins to one
% inch, but as you've probably guessed, you can fiddle with the
% numbers as much as you want.
\usepackage[right=1in,top=1in,left=1in,bottom=1in]{geometry}

% (I have no idea why it's called geometry)

% Up to now we've just provided some information about how the
% document will be structured, and what resources we think we might
% use. If you're familiar with HTML, what we have so far is equivalent
% to what you might put in the <head> section of a document. At this
% point, we can actually get things started. We do that with the
% following command:

\begin{document}

% You could just start typing your masterpiece at this point, but it's
% probably better to give the reader some information first. In
% particular, you may want to include title, author, and date
% information at the beginning of your document. You do that with the
% following commands:

\title{Using Generating Functions to Solve Simple Recurrences}
\author{Richard C Kelley}
\date{\today}
\maketitle

% Note in particular that last one - if you don't have the \maketitle
% command, title, author, and date information won't appear.

% In academic papers especially, it's important to provide a summary
% or abstract of your work after the title. You want to use this to
% catch the reader's attention. In LaTeX you would do that with the
% following pair of commands. Notice that I can just type plain text
% when I'm in the abstract environment.

\begin{abstract}
Generating functions are powerful tools for understanding the behavior
of a sequence of numbers. By making the terms of the sequence the
coefficients of a power series, we can often gain information about
the sequence that would otherwise be hard to obtain. Best of all, when
this method works, we can apply it in almost a completely mechanical
fashion. In this paper we give a simple example that illustrates the
spirit of working with generating functions.
\end{abstract}

% Now we can start writing text. Usually it's considered good taste to
% break up a piece of writing into parts. Unless you hate your reader,
% you should do this as well. In LaTeX, we do this with the following
% command:

\section{Introduction}

% You're probably getting the hang of LaTeX by now. It's just a bunch
% of commands that start with a backslash and optionally have
% arguments enclosed in braces. Once you get this, there's just a
% little more you need to know to be able to comfortably use LaTeX in
% your day to day writing.

% Just as with the abstract, we write plain old text without any
% markup or commands. In particular, we don't need to separate
% paragraphs using any commands as in HTML; we just put a space
% between the paragraphs as you see here:

When we attempt to characterize an algorithm's resource usage in terms
of space, time, bandwidth, or anything else for that matter, we often
end up dealing (explicitly or implicitly) with sequences of
numbers. For example, if we have an algorithm operating on arrays of
numbers, we may want to know how many basic operations our algorithm
performs on an input of size $n$. This measure is often used to
describe the running time of an algorithm, which we'll call
$T$. Moreover, since the running time depends on the input size in
some way, we'll say that $T = T(n)$. This is the standard function
notation, which is just fine. However, it's much more common to think
of functions defined on the natural numbers as being \emph{sequences},
so we'll do that and we'll use the standard notation for sequences
instead of the function notation above. That is, we'll write $T = T_n$
to express the idea that the running time of our algorithm depends on
the parameter $n$.

% If you've been paying attention, a few things should have popped out
% at you in the above paragraph. First, we introduce what's called
% ``math mode.'' You use math mode whenever you want to typeset
% equations or formulas in-line in a paragraph. You enter math mode by
% writing a '$', you write your expression, and then you exit math
% mode by writing another '$'. Also, if you want to write a subscript
% on a variable, you do it by writing an underscore and then the
% subscript. NB: this will only work if your subscript consists of a
% single letter. If it has multiple symbols, you have to enclose the
% subscripted expression in braces. See the examples below.

% LaTeX typesets your writing differently depending on the mode you're
% in. Text you write outside of math mode will appear more or less as
% you type it. In math mode though, letters and spacing are completely
% different. So although this is probably obvious, it bears
% emphasizing - always remember the mode you're in.

% The other new thing you probably noticed was the use of \emph. You
% use this command to write the argument to the command in italics.

% The command \cite{knuth} is a cross reference to an item in the
% bibliography, which you can find at the end of this document.

One of the goals of analysis of algorithms is to, for a given
algorithm, come up with mathematical expressions that describe the
resource usage of the algorithm. Often we only need to know this
information at a very coarse level of detail. When this is the case we
can just look at the asymptotic behavior of our algorithm and estimate
its complexity using ``big-oh'' notation. Sometimes, though, this
isn't good enough, and we'll want more precise estimates of resource
usage. Ideally, such an estimate would be a closed form expression of
the running time in terms of the input size, such as $T_n = n$ or $T_n
= 2^n$. Generating functions give us one way to possibly obtain such
expressions. Even when that isn't possible, the information that
generating functions give us may still provide useful estimates. If
you finish reading this and find the subject interesting, you can find
a lot more about generating functions in computer science in
\cite{knuth}. Or look at some of the other items in the references.

% Sometimes you'll want to display bigger formulas. When this is the
% case, there is another way to enter math mode that will display your
% equations on a new line, centered in the middle of the page:

Looking at things a bit more generally now, let's say we have a
sequence of the form $a_n$, where $n = 0,1,2\ldots$. Then we say that
the \emph{generating function} for the sequence $a_n$ is
% This next line is how we display an equation:
\[ A(x) = \sum_{n=0}^\infty a_n x^n = \sum_{n \ge 0}a_nx^n.\]
So you see, a generating function is just an infinite series such that
the coefficient of $x^n$ is just $a_n$. This may seem like a really
dumb thing to do, but this really is the most powerful way to deal
with sequences of numbers. This is especially true when we aren't
given the sequence explicitly, but are given a \emph{recurrence}.

Before continuing, a somewhat technical point (which means you can
skip to the next paragraph if you don't care about this sort of
thing). If you remember your calculus, you know that infinite series
of the kind described above aren't always \emph{convergent}; that is,
they don't always define a function from the real numbers to the real
numbers. However, for our purposes this doesn't matter. We almost
never care about convergence when we're working with generating
functions, unless for example we're using complex analysis to estimate
the coefficients of the series. So for most purposes we just ignore
the question of convergence and get on with our lives. If this
sloppiness bothers you, rest assured that all of this business about
infinite series can be put on a firm foundation by treating the
infinite series as purely \emph{formal} objects existing in what's
called the \emph{ring of formal power series} (which you would study
in a course on abstract algebra).

% We see a new command here - \ldots. It produces what looks like
% three periods in a row, except that that the spacing is nicer and it
% works well in math mode.

% We also meet some commands for generating symbols. The first of
% these is the \sum command. We use it to display a summation symbol
% (the upper case sigma). After \sum, you see an underscore and then
% {n=0}^\infty. You might guess that _{n=0} means that you write the
% equation n=0 below the summation sign. You'd be right. In general,
% whatever you put in braces following an underscore after the \sum
% command will show up beneath your sum. Similarly, the ^\infty writes
% a symbol on top of the summation sign. In this case, the command
% \infty generates the symbol for ``infinity'' (the sideways 8).

% Incidentally, we write the expression for a generating function in
% two different ways. This shows you the command for writing ``greater
% than or equal,'' from which you should be able to figure out ``less
% than or equal'' (\le). It's also worth noting that when you're
% working with summations, the second form is _much_ easier to work
% with.

% In addition to the \section command, we have the \section*, which
% introduces a new section without a section number.
\section*{An Example}

To demonstrate the power of generating functions when dealing with
recurrences, let's look at an example. Suppose we're working on a
problem, and we come across the following recurrence: $a_0 = 1$ and
$a_n = 2a_{n-1}$. Writing out a few terms of the sequence (always a
good idea) shows us the answer \emph{right} away:
1,2,4,8,16,\ldots. As a computer scientist, you should instantly see
that this is just the sequence of powers of two, so that $a_n =
2^n$. However, we can't always count on brilliant insight to lead us
to the solution to our problems, so let's see if we can get the same
answer using generating functions.

% Sometimes we will want to make an ordered or an unordered list. To
% make an ordered list we use the ``enumerate'' environment, and for
% unordered lists we'll use ``itemize.'' Here's an example showing how
% to make an ordered list using enumerate:

Start by defining our generating function to be $A(x) =
\sum_{n\ge0}a_nx^n$. We then go through the following steps:
\begin{enumerate}
\item
  Rewrite your recurrence so that a single equation captures all the
  parts in the definition of the recurrence.
\item
  Multiply each side of your recurrence by $x^n$.
\item
  Sum over all values of $n$ for which the recurrence is defined.
\item
  You now have an expression in terms of infinite series - convert
  this into an equation involving the unknown generating function (in
  our example, $A(x)$).
\item
  Solve the \emph{functional equation} you got in the previous step to
  find a closed-form expression for your generating function in terms
  of the variable $x$.
\item
  Expand the closed form expression from the previous step to
  (hopefully) get a closed-form expression for your sequence in terms
  of $n$.
\end{enumerate}
Let's start with the first rule. We need a single equation to cover
\emph{both} the case where $n=0$ and the case where $n>0$. For the
second case, we can use the equation $a_n = 2a_{n-1}$. But when $n=0$
this equation is doesn't really make sense: $a_{-1}$ isn't
defined. However, if we agree that $a_n = 0$ for all $n < 0$, then we
can get around that problem. Even so, the equation is still not true:
$a_0 = 1$ and $2a_{-1} = 0$.

% You may have noticed that when we put something in quotes, we don't
% actually use the double quote key on the keyboard. We write our open
% quotes with two `s and we write our close quotes with two 's, as you
% see here:

To get around this, we introduce a useful ``trick.'' It's called
\emph{Iverson's convention}, and has a tendency to make life easier
when working with summations. The convention to take any predicate
(statement that can be true or false), enclose it in square brackets,
and let it evaluate to 1 if the predicate is true and 0 if it's
false. In other words, if $P(x)$ is our predicate, we have
\begin{equation*}
[P(x)] = \left\{
\begin{array}{rl}
  1 & \text{if } P(x) \text{ is true} \\
  0 & \text{otherwise}
\end{array} \right.
\end{equation*}
Now we rewrite our recurrence as follows: We get rid of the
special case $a_0 = 1$ and write the second case as $a_n = 2a_{n-1} +
[n=0]$. Then for $n \ge 1$, the term $[n=0]$ evaluates to 0 and
doesn't affect the recurrence. But for the case where $n$ \emph{is} 0,
the equation still works out:
\begin{align}
  a_{0} &= 2a_{0-1} + [0=0] \\
  &= 2 * 0 + 1 \\
  &= 1
\end{align}
So our single new equation agrees with our old pair of equations for
all possible values of the input, which means that both approaches
define the same sequence. All is well in the mathematical universe.

% Two really critical things in that last paragraph. The first
% environment we use (equation*) to introduce a function that is
% defined in parts. The second enviroment we use (align) is for
% multiple equations. This environment is great when you want to show
% your work. The '&' in both environments tells LaTeX where to perform
% the alignment - right before the text in the first case, and right
% before the equals sign in the second. The double backslash \\ tells
% LaTeX to start a new line, and is necessary to prevent the parts of
% our definition or derivation from running together.

Now we can apply the next two steps of our procedure to get the
following:
\[ \sum_{n\ge0} a_nx^n = 2 \sum_{n\ge0}a_{n-1}x^n + 1.\]
(That second term on the right evaluates to 1 because it's $[n=0]x^n$,
which is zero for everything but $n=0$ and 1 at $n=0$.) The left side
of that equation is easy: it's just $A(x)$. The right side requires a
bit of work. In particular, we need to figure out how to express
$\sum_{n\ge0}a_{n-1}x^n$ in terms of our (currently unknown) function
$A(x)$. But that's easy. We can pull an $x$ out of the sum and make a
change of variables (for $n$) to get the following:
\begin{align}
  \sum_{n\ge0}a_{n-1}x^n &= x \sum_{n\ge0}a_{n-1}x^{n-1} \\
  &= x \sum_{n+1 \ge 0}a_{(n+1)-1}x^{(n+1)-1} \\
  &= x \sum_{n \ge -1}a_nx^n \\
  &= x \sum_{n \ge 0}x_nx^n \\
  &= xA(x),
\end{align}
where we can go from equation 6 to equation 7 because when $n = -1$,
the term $a_nx^n$ equals zero. (You agreed to that, remember?)

% This next paragraph shows us how to write fractions, which can
% sometimes be useful:

So now we have the functional equation
\[ A(x) = 2xA(x) + 1, \]
which we can solve for $A(x)$ using just algebra to get
\[ A(x) = \frac{1}{1-2x}.\]
So there. This is our generating function for the sequence
$a_n$. It may not seem like it, but we now know a lot more about our
sequence than we did when we started. For example, suppose we want to
find a closed form expression for $a_n$. Then we can expand $A(x)$ as
a power series in $x$ to get our answer. There are a few ways to do
this:
\begin{itemize}
  \item
    Use calculus to figure out the answer from scratch.
  \item
    Know the answer
  \item
    Look it up.
\end{itemize}
The first method is the most reliable and versatile. In this case
though, we can use the second or third methods (because we remember
from calculus that $1/(1-x) = \sum x^n$) to see that
% Notice that we can enter either the align or the align*
% environment. The first one numbers the equations. The second one
% does not.
\begin{align*}
  A(x) &= \sum_{n\ge0}(2x)^n \\
  &= \sum_{n\ge0}2^n x^n.
\end{align*}
Since two formal power series are equal if and only if the
coefficients on corresponding terms are equal, we can see from the
equation
\[ \sum_{n\ge0}a_nx^n = \sum_{n\ge0}2^nx^n\]
that $a_n = 2^n$.

That probably seemed like a lot of work to come to a really simple
conclusion. For this particular problem, it's probably true that the
generating function approach is overkill. However, for more
complicated problems, it's unlikely that you'll be able to just see
the answer, and it may be the case that generating functions are the
only way to go.

\section*{A Fun Problem}
Consider a checkerboard with dimensions $2 \times n$. Suppose we want
to cover this board with $2 \times 1$ tiles in such a way that the
entire board is covered with tiles and no two tiles overlap. Clearly
this can be done. The question here is: how many ways are there to do
it? \emph{Hint:} Let the number of ways to tile a $2 \times n$ board
with $2 \times 1$ tiles be denoted $f_n$. Try answering the question
for small values of $n$ to find a pattern. (You'll probably see it
right away. The real meat of this problem is to \emph{prove} the
relationship.) Define a recurrence for $f_n$, and \emph{prove} that
your recurrence is correct. One way to do this is by induction on
$n$. Once you have your recurrence, see if you can find the generating
function for your sequence, and expand the generating function you
find as a power series to find a closed form (\emph{non}recursive)
expression for $f_n$ in terms of $n$.

\section{Further Reading}
The study of generating functions is generally considered a part of
the branch of mathematics called \emph{Combinatorics}, or discrete
math. You can find the above problem and a lot of other fun counting
problems in \cite{brualdi}. Other equally fun but \emph{much} more
challenging problems (often involving more advanced math like algebra
and topology) can be found in \cite{stanley}. Another challenging book
from a computer science perspective is the very entertaining
\cite{graham}. If you're the practical type, you can find similar
problems of an applied nature in \cite{roberts}.

% If you ever have to cite any sources, you'll need a references
% section. One of the nicest things about LaTeX is the way it makes
% references and citations so easy. Here's how it works:

% We start by entering the bibliography environment. You can read the
% {9} as saying that you will have fewer than 10 items in your
% bibliography. The other common number to put there is 99.
\begin{thebibliography}{9}

% We introduce a new item in the bibliography with the \bibitem
% command. The argument to the bibitem command is a key that allows
% you to refer to this item in the text.
\bibitem{knuth}
  Donald Knuth, \emph{The Art of Computer Programming, Volume 1:
    Fundamental Algorithms},
  Addison-Wesley, 1997.

\bibitem{brualdi}
  Richard Brualdi, \emph{Introductory Combinatorics}, Prentice Hall,
  2004.

\bibitem{stanley}
  Richard Stanley, \emph{Enumerative Combinatorics}, Cambridge
  University Press, 2001.

\bibitem{graham}
  Ronald Graham, Donald Knuth, Oren Patashnik, \emph{Concrete
    Mathematics: A Foundation for Computer Science}, Addison-Wesley
  Professional, 1994.

\bibitem{roberts}
  Fred Roberts, Barry Tesman, \emph{Applied Combinatorics}, Prentice
  Hall, 2003.
\end{thebibliography}


% Last but not least, we end our document with the following command:
\end{document}
	% A Simple LaTeX Example
	% Author: Richard C Kelley

	% This is a comment. A comment begins with a '%' and extends to the
	% end of the line.

	% We always start our LaTeX documents by specifying the document class
	% we want to use. There are several document classes available that
	% you could use if you wanted - article, book, report, letter,
	% etc. For many purposes, though, all you need is the article
	% class. You specify the document class with the following command:
	\documentclass{article}

	% Once we've specified the document class, we will probably want to
	% include some packages. A package extends the basic set of commands
	% and symbols that comes with LaTeX, and there are a few that are
	% almost always useful. Those are the ones we include here:

	% The first two packages listed below are from the American
	% Mathematical Society, and include symbols and formatting options
	% that make it much easier to typeset mathematics. The last package,
	% verbatim, gives us an enviroment like <pre> in HTML, and is useful
	% for typesetting computer code.
	\usepackage{amsmath,amssymb,verbatim}

	% If we want, we can have multiple \usepackage commands in our input
	% file. The default margins in LaTeX are pretty big, so I like to make
	% them smaller using this command. Here I set all the margins to one
	% inch, but as you've probably guessed, you can fiddle with the
	% numbers as much as you want.
	\usepackage[right=1in,top=1in,left=1in,bottom=1in]{geometry}

	% (I have no idea why it's called geometry)

	% Up to now we've just provided some information about how the
	% document will be structured, and what resources we think we might
	% use. If you're familiar with HTML, what we have so far is equivalent
	% to what you might put in the <head> section of a document. At this
	% point, we can actually get things started. We do that with the
	% following command:

	\begin{document}

	% You could just start typing your masterpiece at this point, but it's
	% probably better to give the reader some information first. In
	% particular, you may want to include title, author, and date
	% information at the beginning of your document. You do that with the
	% following commands:

	\title{Using Generating Functions to Solve Simple Recurrences}
	\author{Richard C Kelley}
	\date{\today}
	\maketitle

	% Note in particular that last one - if you don't have the \maketitle
	% command, title, author, and date information won't appear.

	% In academic papers especially, it's important to provide a summary
	% or abstract of your work after the title. You want to use this to
	% catch the reader's attention. In LaTeX you would do that with the
	% following pair of commands. Notice that I can just type plain text
	% when I'm in the abstract environment.

	\begin{abstract}
	Generating functions are powerful tools for understanding the behavior
	of a sequence of numbers. By making the terms of the sequence the
	coefficients of a power series, we can often gain information about
	the sequence that would otherwise be hard to obtain. Best of all, when
	this method works, we can apply it in almost a completely mechanical
	fashion. In this paper we give a simple example that illustrates the
	spirit of working with generating functions.
	\end{abstract}

	% Now we can start writing text. Usually it's considered good taste to
	% break up a piece of writing into parts. Unless you hate your reader,
	% you should do this as well. In LaTeX, we do this with the following
	% command:

	\section{Introduction}

	% You're probably getting the hang of LaTeX by now. It's just a bunch
	% of commands that start with a backslash and optionally have
	% arguments enclosed in braces. Once you get this, there's just a
	% little more you need to know to be able to comfortably use LaTeX in
	% your day to day writing.

	% Just as with the abstract, we write plain old text without any
	% markup or commands. In particular, we don't need to separate
	% paragraphs using any commands as in HTML; we just put a space
	% between the paragraphs as you see here:

	When we attempt to characterize an algorithm's resource usage in terms
	of space, time, bandwidth, or anything else for that matter, we often
	end up dealing (explicitly or implicitly) with sequences of
	numbers. For example, if we have an algorithm operating on arrays of
	numbers, we may want to know how many basic operations our algorithm
	performs on an input of size $n$. This measure is often used to
	describe the running time of an algorithm, which we'll call
	$T$. Moreover, since the running time depends on the input size in
	some way, we'll say that $T = T(n)$. This is the standard function
	notation, which is just fine. However, it's much more common to think
	of functions defined on the natural numbers as being \emph{sequences},
	so we'll do that and we'll use the standard notation for sequences
	instead of the function notation above. That is, we'll write $T = T_n$
	to express the idea that the running time of our algorithm depends on
	the parameter $n$.

	% If you've been paying attention, a few things should have popped out
	% at you in the above paragraph. First, we introduce what's called
	% ``math mode.'' You use math mode whenever you want to typeset
	% equations or formulas in-line in a paragraph. You enter math mode by
	% writing a '$', you write your expression, and then you exit math
	% mode by writing another '$'. Also, if you want to write a subscript
	% on a variable, you do it by writing an underscore and then the
	% subscript. NB: this will only work if your subscript consists of a
	% single letter. If it has multiple symbols, you have to enclose the
	% subscripted expression in braces. See the examples below.

	% LaTeX typesets your writing differently depending on the mode you're
	% in. Text you write outside of math mode will appear more or less as
	% you type it. In math mode though, letters and spacing are completely
	% different. So although this is probably obvious, it bears
	% emphasizing - always remember the mode you're in.

	% The other new thing you probably noticed was the use of \emph. You
	% use this command to write the argument to the command in italics.

	% The command \cite{knuth} is a cross reference to an item in the
	% bibliography, which you can find at the end of this document.

	One of the goals of analysis of algorithms is to, for a given
	algorithm, come up with mathematical expressions that describe the
	resource usage of the algorithm. Often we only need to know this
	information at a very coarse level of detail. When this is the case we
	can just look at the asymptotic behavior of our algorithm and estimate
	its complexity using ``big-oh'' notation. Sometimes, though, this
	isn't good enough, and we'll want more precise estimates of resource
	usage. Ideally, such an estimate would be a closed form expression of
	the running time in terms of the input size, such as $T_n = n$ or $T_n
	= 2^n$. Generating functions give us one way to possibly obtain such
	expressions. Even when that isn't possible, the information that
	generating functions give us may still provide useful estimates. If
	you finish reading this and find the subject interesting, you can find
	a lot more about generating functions in computer science in
	\cite{knuth}. Or look at some of the other items in the references.

	% Sometimes you'll want to display bigger formulas. When this is the
	% case, there is another way to enter math mode that will display your
	% equations on a new line, centered in the middle of the page:

	Looking at things a bit more generally now, let's say we have a
	sequence of the form $a_n$, where $n = 0,1,2\ldots$. Then we say that
	the \emph{generating function} for the sequence $a_n$ is
	% This next line is how we display an equation:
	\[ A(x) = \sum_{n=0}^\infty a_n x^n = \sum_{n \ge 0}a_nx^n.\]
	So you see, a generating function is just an infinite series such that
	the coefficient of $x^n$ is just $a_n$. This may seem like a really
	dumb thing to do, but this really is the most powerful way to deal
	with sequences of numbers. This is especially true when we aren't
	given the sequence explicitly, but are given a \emph{recurrence}.

	Before continuing, a somewhat technical point (which means you can
	skip to the next paragraph if you don't care about this sort of
	thing). If you remember your calculus, you know that infinite series
	of the kind described above aren't always \emph{convergent}; that is,
	they don't always define a function from the real numbers to the real
	numbers. However, for our purposes this doesn't matter. We almost
	never care about convergence when we're working with generating
	functions, unless for example we're using complex analysis to estimate
	the coefficients of the series. So for most purposes we just ignore
	the question of convergence and get on with our lives. If this
	sloppiness bothers you, rest assured that all of this business about
	infinite series can be put on a firm foundation by treating the
	infinite series as purely \emph{formal} objects existing in what's
	called the \emph{ring of formal power series} (which you would study
	in a course on abstract algebra).

	% We see a new command here - \ldots. It produces what looks like
	% three periods in a row, except that that the spacing is nicer and it
	% works well in math mode.

	% We also meet some commands for generating symbols. The first of
	% these is the \sum command. We use it to display a summation symbol
	% (the upper case sigma). After \sum, you see an underscore and then
	% {n=0}^\infty. You might guess that _{n=0} means that you write the
	% equation n=0 below the summation sign. You'd be right. In general,
	% whatever you put in braces following an underscore after the \sum
	% command will show up beneath your sum. Similarly, the ^\infty writes
	% a symbol on top of the summation sign. In this case, the command
	% \infty generates the symbol for ``infinity'' (the sideways 8).

	% Incidentally, we write the expression for a generating function in
	% two different ways. This shows you the command for writing ``greater
	% than or equal,'' from which you should be able to figure out ``less
	% than or equal'' (\le). It's also worth noting that when you're
	% working with summations, the second form is _much_ easier to work
	% with.

	% In addition to the \section command, we have the \section*, which
	% introduces a new section without a section number.
	\section*{An Example}

	To demonstrate the power of generating functions when dealing with
	recurrences, let's look at an example. Suppose we're working on a
	problem, and we come across the following recurrence: $a_0 = 1$ and
	$a_n = 2a_{n-1}$. Writing out a few terms of the sequence (always a
	good idea) shows us the answer \emph{right} away:
	1,2,4,8,16,\ldots. As a computer scientist, you should instantly see
	that this is just the sequence of powers of two, so that $a_n =
	2^n$. However, we can't always count on brilliant insight to lead us
	to the solution to our problems, so let's see if we can get the same
	answer using generating functions.

	% Sometimes we will want to make an ordered or an unordered list. To
	% make an ordered list we use the ``enumerate'' environment, and for
	% unordered lists we'll use ``itemize.'' Here's an example showing how
	% to make an ordered list using enumerate:

	Start by defining our generating function to be $A(x) =
	\sum_{n\ge0}a_nx^n$. We then go through the following steps:
	\begin{enumerate}
	\item
	Rewrite your recurrence so that a single equation captures all the
	parts in the definition of the recurrence.
	\item
	Multiply each side of your recurrence by $x^n$.
	\item
	Sum over all values of $n$ for which the recurrence is defined.
	\item
	You now have an expression in terms of infinite series - convert
	this into an equation involving the unknown generating function (in
	our example, $A(x)$).
	\item
	Solve the \emph{functional equation} you got in the previous step to
	find a closed-form expression for your generating function in terms
	of the variable $x$.
	\item
	Expand the closed form expression from the previous step to
	(hopefully) get a closed-form expression for your sequence in terms
	of $n$.
	\end{enumerate}
	Let's start with the first rule. We need a single equation to cover
	\emph{both} the case where $n=0$ and the case where $n>0$. For the
	second case, we can use the equation $a_n = 2a_{n-1}$. But when $n=0$
	this equation is doesn't really make sense: $a_{-1}$ isn't
	defined. However, if we agree that $a_n = 0$ for all $n < 0$, then we
	can get around that problem. Even so, the equation is still not true:
	$a_0 = 1$ and $2a_{-1} = 0$.

	% You may have noticed that when we put something in quotes, we don't
	% actually use the double quote key on the keyboard. We write our open
	% quotes with two `s and we write our close quotes with two 's, as you
	% see here:

	To get around this, we introduce a useful ``trick.'' It's called
	\emph{Iverson's convention}, and has a tendency to make life easier
	when working with summations. The convention to take any predicate
	(statement that can be true or false), enclose it in square brackets,
	and let it evaluate to 1 if the predicate is true and 0 if it's
	false. In other words, if $P(x)$ is our predicate, we have
	\begin{equation*}
	[P(x)] = \left\{
	\begin{array}{rl}
	1 & \text{if } P(x) \text{ is true} \\
	0 & \text{otherwise}
	\end{array} \right.
	\end{equation*}
	Now we rewrite our recurrence as follows: We get rid of the
	special case $a_0 = 1$ and write the second case as $a_n = 2a_{n-1} +
	[n=0]$. Then for $n \ge 1$, the term $[n=0]$ evaluates to 0 and
	doesn't affect the recurrence. But for the case where $n$ \emph{is} 0,
	the equation still works out:
	\begin{align}
	a_{0} &= 2a_{0-1} + [0=0] \\
	&= 2 * 0 + 1 \\
	&= 1
	\end{align}
	So our single new equation agrees with our old pair of equations for
	all possible values of the input, which means that both approaches
	define the same sequence. All is well in the mathematical universe.

	% Two really critical things in that last paragraph. The first
	% environment we use (equation*) to introduce a function that is
	% defined in parts. The second enviroment we use (align) is for
	% multiple equations. This environment is great when you want to show
	% your work. The '&' in both environments tells LaTeX where to perform
	% the alignment - right before the text in the first case, and right
	% before the equals sign in the second. The double backslash \\ tells
	% LaTeX to start a new line, and is necessary to prevent the parts of
	% our definition or derivation from running together.

	Now we can apply the next two steps of our procedure to get the
	following:
	\[ \sum_{n\ge0} a_nx^n = 2 \sum_{n\ge0}a_{n-1}x^n + 1.\]
	(That second term on the right evaluates to 1 because it's $[n=0]x^n$,
	which is zero for everything but $n=0$ and 1 at $n=0$.) The left side
	of that equation is easy: it's just $A(x)$. The right side requires a
	bit of work. In particular, we need to figure out how to express
	$\sum_{n\ge0}a_{n-1}x^n$ in terms of our (currently unknown) function
	$A(x)$. But that's easy. We can pull an $x$ out of the sum and make a
	change of variables (for $n$) to get the following:
	\begin{align}
	\sum_{n\ge0}a_{n-1}x^n &= x \sum_{n\ge0}a_{n-1}x^{n-1} \\
	&= x \sum_{n+1 \ge 0}a_{(n+1)-1}x^{(n+1)-1} \\
	&= x \sum_{n \ge -1}a_nx^n \\
	&= x \sum_{n \ge 0}x_nx^n \\
	&= xA(x),
	\end{align}
	where we can go from equation 6 to equation 7 because when $n = -1$,
	the term $a_nx^n$ equals zero. (You agreed to that, remember?)

	% This next paragraph shows us how to write fractions, which can
	% sometimes be useful:

	So now we have the functional equation
	\[ A(x) = 2xA(x) + 1, \]
	which we can solve for $A(x)$ using just algebra to get
	\[ A(x) = \frac{1}{1-2x}.\]
	So there. This is our generating function for the sequence
	$a_n$. It may not seem like it, but we now know a lot more about our
	sequence than we did when we started. For example, suppose we want to
	find a closed form expression for $a_n$. Then we can expand $A(x)$ as
	a power series in $x$ to get our answer. There are a few ways to do
	this:
	\begin{itemize}
	\item
	Use calculus to figure out the answer from scratch.
	\item
	Know the answer
	\item
	Look it up.
	\end{itemize}
	The first method is the most reliable and versatile. In this case
	though, we can use the second or third methods (because we remember
	from calculus that $1/(1-x) = \sum x^n$) to see that
	% Notice that we can enter either the align or the align*
	% environment. The first one numbers the equations. The second one
	% does not.
	\begin{align*}
	A(x) &= \sum_{n\ge0}(2x)^n \\
	&= \sum_{n\ge0}2^n x^n.
	\end{align*}
	Since two formal power series are equal if and only if the
	coefficients on corresponding terms are equal, we can see from the
	equation
	\[ \sum_{n\ge0}a_nx^n = \sum_{n\ge0}2^nx^n\]
	that $a_n = 2^n$.

	That probably seemed like a lot of work to come to a really simple
	conclusion. For this particular problem, it's probably true that the
	generating function approach is overkill. However, for more
	complicated problems, it's unlikely that you'll be able to just see
	the answer, and it may be the case that generating functions are the
	only way to go.

	\section*{A Fun Problem}
	Consider a checkerboard with dimensions $2 \times n$. Suppose we want
	to cover this board with $2 \times 1$ tiles in such a way that the
	entire board is covered with tiles and no two tiles overlap. Clearly
	this can be done. The question here is: how many ways are there to do
	it? \emph{Hint:} Let the number of ways to tile a $2 \times n$ board
	with $2 \times 1$ tiles be denoted $f_n$. Try answering the question
	for small values of $n$ to find a pattern. (You'll probably see it
	right away. The real meat of this problem is to \emph{prove} the
	relationship.) Define a recurrence for $f_n$, and \emph{prove} that
	your recurrence is correct. One way to do this is by induction on
	$n$. Once you have your recurrence, see if you can find the generating
	function for your sequence, and expand the generating function you
	find as a power series to find a closed form (\emph{non}recursive)
	expression for $f_n$ in terms of $n$.

	\section{Further Reading}
	The study of generating functions is generally considered a part of
	the branch of mathematics called \emph{Combinatorics}, or discrete
	math. You can find the above problem and a lot of other fun counting
	problems in \cite{brualdi}. Other equally fun but \emph{much} more
	challenging problems (often involving more advanced math like algebra
	and topology) can be found in \cite{stanley}. Another challenging book
	from a computer science perspective is the very entertaining
	\cite{graham}. If you're the practical type, you can find similar
	problems of an applied nature in \cite{roberts}.

	% If you ever have to cite any sources, you'll need a references
	% section. One of the nicest things about LaTeX is the way it makes
	% references and citations so easy. Here's how it works:

	% We start by entering the bibliography environment. You can read the
	% {9} as saying that you will have fewer than 10 items in your
	% bibliography. The other common number to put there is 99.
	\begin{thebibliography}{9}

	% We introduce a new item in the bibliography with the \bibitem
	% command. The argument to the bibitem command is a key that allows
	% you to refer to this item in the text.
	\bibitem{knuth}
	Donald Knuth, \emph{The Art of Computer Programming, Volume 1:
	Fundamental Algorithms},
	Addison-Wesley, 1997.

	\bibitem{brualdi}
	Richard Brualdi, \emph{Introductory Combinatorics}, Prentice Hall,
	2004.

	\bibitem{stanley}
	Richard Stanley, \emph{Enumerative Combinatorics}, Cambridge
	University Press, 2001.

	\bibitem{graham}
	Ronald Graham, Donald Knuth, Oren Patashnik, \emph{Concrete
	Mathematics: A Foundation for Computer Science}, Addison-Wesley
	Professional, 1994.

	\bibitem{roberts}
	Fred Roberts, Barry Tesman, \emph{Applied Combinatorics}, Prentice
	Hall, 2003.
	\end{thebibliography}


	% Last but not least, we end our document with the following command:
	\end{document}