\documentclass[11pt]{report}
\usepackage{times}
\pagestyle{empty}
\def\nl{\hspace*{\fill}\\}
\def\bs{\hspace*{-1.2em}}
\def\bd{\begin{description}}
\def\ed{\end{description}}
\def\ra{\rightarrow}
\def\ul{\underline}
\def\0{_{\phantom0}}
\setlength{\parindent}{0em}
\setlength{\parskip}{1ex}
\pagestyle{empty}
% \addtolength{\textwidth}{1in}
% \addtolength{\evensidemargin}{-.5in}
% \addtolength{\oddsidemargin}{-.5in}
\addtolength{\textheight}{1.75in}
\addtolength{\topmargin}{-.875in}
\begin{document}
\begin{center}
{\bf Freshman Seminar 24i: Mathematical Problem Solving}
\\
Some problems on generating functions
\end{center}

Some more examples using finite generating functions
(we might call them ``generating polynomials''):

1. Find a formula for the alternating sum
  $$
  \sum_{k=0}^n (-1)^k {n \choose k}^{\!2}
  = {n\choose 0}^{\!2}
  - {n\choose 1}^{\!2}
  + {n\choose 2}^{\!2}
  - + \cdots \pm {n\choose n}^{\!2}
  $$
  of the squares of the entries of the $n$-th row of Pascal's triangle.
  (We showed Monday that the sum of the squares is $2n \choose n$.)
  Make sure to check that your answer agrees with the first few cases
  such as
  $$
  1^2 - 2^2 + 1^2 = -2, \quad
  1^2 - 3^2 + 3^2 - 1^2 = 0, \quad
  1^2 - 4^2 + 6^2 - 4^2 + 1^2 = 6.
  $$
  [It's OK to give your answer in a form that depends on the parity of~$n$,
  i.e.\ one formula for even~$n$, another for odd~$n$.  \LaTeX\ provides
  a \verb+\cases+ command for such expressions.]

2. i) Prove that if a fair coin is thrown $n>0$ times then the total
number of heads is even with probability exactly 50\%.\nl
ii) If a fair coin is thrown $100$ times, is the probability that
the total number of heads is a multiple of~$4$ equal to, greater than,
or less than 25\%, and (if not equal) by how much?
[Hint: expand $(1+i)^n$.]

3. [From my old Chess and Math seminar]  Use the expansion
$$
(1+x+x^2)^7 = x^{14} + 7 x^{13} + 28 x^{12} + 77 x^{11} + 161 x^{10}
  + 266 x^9 + 357 x^8 \qquad\qquad
$$ \vspace {-4ex} $$
\qquad\qquad\qquad
  {} + 393 x^7 + 357 x^6 + 266 x^5 + 161 x^4 + 77 x^3 + 28 x^2 + 7 x + 1
$$
to count the number of $7$-move King paths from e1 to e8 (that is,
{}from $(5,1)$ to $(5,8)$ on the standard $8\times 8$ chessboard).
How many \hbox{$7$-move} King paths are there from e1 to~f8 or~g8?
(Careful here!) What chess enumeration problem is solved by
he constant coefficient of the ``Laurent polynomial''
$$
(xy + x + xy^{-1} + y + y^{-1} + x^{-1}y + x^{-1} + x^{-1}y^{-1})^6~?
$$
4. [Another chess enumeration, this one giving rise to a power series,
 not a polynomial.]
 A Knight starts on square b1 (the middle square of the bottom row)
 of a $3 \times n$ chessboard, and is allowed to move only forward,
 so it has two options at each turn (from b1 to a3 or c3, from a3 to
 c4 or b5, etc.).  For each $n=1,2,3,\ldots$,
 let $a_n$ and $b_n$ be the number of paths from
 b1 to a$n$ and b$n$ respectively.  Show that for $n>2$
 we have $a_n = a_{n-1} + b_{n-2}$ and $b_n = 2 a_{n-2}$.  Use this
 to set up equations for the generating functions
 \begin{eqnarray*}
 A & \!\! = \!\! & \sum_{n=1}^\infty a_n t^n \, = \,
 t^3 + t^4 + t^5 + t^6 + 3t^7 + 5t^8 + 7t^9 + 9t^{10} + 15t^{11} + \cdots,
 \\
 B & \!\! = \!\! & \sum_{n=1}^\infty b_n t^n \, = \,
 t + 2t^5 + 2t^6 + 2t^7 + 2t^8 + 6t^9 + 10t^{10} + 14t^{11} + \cdots,
 \end{eqnarray*}
 and solve them to recover $A$ and~$B$\/ as rational functions of~$t$.

\pagebreak

More examples of using (infinite) generating functions
to prove identities:
 
5. Let $A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$ be the
  generating function associated to the sequence $\{a_n\}_{n=0}^\infty$.
  What is the generating function associated to the sequence of partial
  sums $s_n = a_0 + a_1 + a_2 + \cdots + a_n$?  Use this to give
  an alternative proof of the ``hockey stick identity''
  ${k \choose k} + {k+1 \choose k} + {k+2 \choose k}
  + \cdots + {n \choose k} = {n+1 \choose k+1}$
  and to check the formula for the sum of the first $n$ Fibonacci numbers
  (if you don't know this formula you should be able to easily surmise it
  and then prove it by induction).

6. Let $\varphi = (1+\sqrt5) / 2$ be the Golden Ratio and
  $\bar\varphi = (1-\sqrt5) / 2$ its algebraic conjugate.
  Check that
  $$
  \varphi + \bar\varphi = 1,
  \quad
  \varphi \bar\varphi = -1,
  \quad
  \varphi - \bar\varphi = \sqrt{5}.
  $$
  Using these identities,\footnote{
    Trust me, this is easier than working directly with
    the explicit form $(1 \pm \sqrt5) / 2$ of $\varphi$ and $\varphi'$.
    }
  check that $1-x-x^2 = (1-\varphi x) (1 - \bar\varphi x)$, and find
  the coefficients $a, \bar a$ of the ``partial fraction decomposition''
  $$
  \frac1{1-x-x^2} = \frac{a}{1-\varphi x} + \frac{\bar a}{1 - \bar\varphi x}.
  $$
  Use this to derive the formula for the \hbox{$n$-th} Fibonacci number
  in terms of~$\varphi$ and $\bar\varphi$.

\vspace*{2ex}

Generating functions and partitions:

7. A ``partition'' of a natural number~$n$ is a decomposition of~$n$
  as a sum of natural numbers (the ``parts''), without regard to order.
  For example, $3 + 1 + 1$ and $1 + 3 + 1$ are the same partition of~$5$;
  equivalently, we may require the parts to be listed in
  non-increasing order, as we do later in this and the next problem.
  The number of partitions of~$n$ is denoted by $p_n$.
  For example: $p_5 = 7$, the seven partitions of~$5$ being
  $$
  5,\ \ 4+1,\ \ 3+2,\ \ 3+1+1,\ \ 2+2+1,\ \ 2+1+1+1,\ \ 1+1+1+1+1.
  $$
  We deem $p_0$ to equal~$1$.  Prove that the generating function
  $\sum_{n=0}^\infty p_n x^n$ equals\footnote{
    $\prod = \Pi$roduct, used in the same way as $\sum = \Sigma$um.
    }
  $$
  \prod_{m=1}^\infty \frac1{1-x^m}
  = \frac1{1-x} \,
   \frac1{1-x^2} \,
   \frac1{1-x^3} \,
   \frac1{1-x^4} \,
   \cdots.
  $$
  More generally, for any $a_1,a_2,a_3,\ldots$ the number of partitions
  of~$n$ each of whose parts is one of $a_1,a_2,a_3,\ldots$ is
  the coefficient of~$x^n$ in $\prod_i 1/(1-x^{a_i})$.
  For example, the number of different ways to settle an
  \hbox{$n$-cent} debt in U.S.~coins is the $x^n$~coefficient in
  $$
  \frac1{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100})}
  $$
  (but good luck finding a 50-cent piece).  How would you adjust
  this formula to reflect the fact that there are actually two
  kinds of dollar coins in circulation?  What if you cannot use
  more than $15$ pennies (in accordance with the urban myth that
  $16$ or more pennies are not legal tender)?

8. Prove that the number of partitions of an integer~$n$ with
  no part divisible by~$3$ is the same as the number of partitions
  of~$n$ with no part repeated more than twice.   (For example, when
  $n=6$ the first count omits only the four partitions $6$, $3+3$,
  $3+2+1$, $3+1+1+1$, and the second count only $2+2+2$, $3+1+1+1$,
  $2+1+1+1+1+1$, $1+1+1+1+1+1$, so both counts are $p_6-4$.) Generalize.

\pagebreak

Exponential generating functions:

9. For sequences $\{\alpha_n\}_{n=0}^\infty$, $\{\beta_n\}_{n=0}^\infty$
  let $A(x) = \sum_{n=0}^\infty \alpha_n x^n/n!$ and
  $B(x) = \sum_{n=0}^\infty \beta_n x^n/n!$ be the
  exponential generating functions.
  What is the ``exponential convolution'' sequence, call it
  $\{\gamma_n\}_{n=0}^\infty$, whose exponential generating function
  $\sum_{n=0}^\infty \gamma_n x^n/n!$ is $A(x) B(x)$?
  (This should give you a sense of one kind of context where you might
  prefer to use exponential rather than ordinary generating functions.)

10. Define numbers $\beta_n$ by the exponential generating function
  $$
  \beta_0 + \beta_1 x + \beta_2 \frac{x^2}{2!} + \beta_3 \frac{x^2}{3!}
  + \cdots
  = \sum_{n=0}^\infty \beta_n \frac{x^n}{n!}
  = \frac{t}{e^t-1}.
  $$
  Compute at least $\beta_0$ through $\beta_7$
  (you're welcome to use a computer package,
  but please make sure you get answers such as
  $\beta_4 = -1/30$ rather than $\beta_4 = -0.03333\ldots$).

  i) What pattern do you observe for the odd-order coefficients $\beta_{2m+1}$?
  Prove it.

  ii) Define polynomials $b_n(t)$ by
  $$
  b_n(t) = \sum_{m=0}^n {n \choose m} \beta_m t^{n-m} =
  t^n
  + n \beta_1 t^{n-1}
  + {n \choose 2} \beta_2 t^{n-2}
  + \cdots
  + {n \choose n} \beta_n.
  $$
  [This expression is sometimes denoted by ``$(\beta + t)^{[n]}$'':
  expand $(\beta + t)^n$ binomially and replace each factor $\beta^m$
  by $\beta_m$.]  Find a formula for the exponential generating function
  $\sum_{n=0}^\infty b_n(t) x^n / n!$,
  and use it to prove the identity $b_n(t+1) - b_n(t) = n t^{n-1}$.
  It follows that for $t=1,2,3\ldots$ we have
  $$
  1 + 2^n + 3^n + \cdots + t^n = \frac1{n+1} (b_{n+1}(t) - \beta_{n+1}).
  $$
  Thus these $\beta_n$ let us generalize the familiar formulas for the
  sums of the first $t$ natural numbers and their squares.
\end{document}
