\documentclass[12pt]{article}
\pagestyle{empty}
\begin{document}
\large
\begin{center}
Math 491, Take-home Midterm \\
(due October 28, 9:30 a.m.)
\end{center}
\medskip
Do all of the following problems:
\begin{enumerate}
\item %1
\begin{itemize}
\item[(a)]
(20 points) For $n \geq 1$,
let $a_n$ be the number of ways to put pennies
on the cells of a 2-by-$n$ rectangle
(at most one penny per cell)
so that no two pennies are horizontally or vertically adjacent.
Thus $a_1=3$, $a_2=7$, $a_3=17$, etc.
Express the generating function $\sum_{n \geq 1} a_n x^n$
as a rational function of $x$,
and give a formula for $a_n$.
\item[(b)]
(20 points) For $n \geq 2$,
let $b_n$ be the number of ways to put pennies
on the cells of a 2-by-$n$ rectangle
(at most one penny per cell)
so that no two pennies are horizontally or vertically adjacent,
where now the rectangle has been wrapped around to form a cylinder,
so that pennies in the two upper corners (or pennies in the two lower corners)
are considered adjacent: $b_2=7$, $b_3=13$, etc.
Express the generating function $\sum_{n \geq 2} b_n x^n$
as a rational function of $x$,
and give a formula for $b_n$.
\end{itemize}
\item %2
Consider all finite sequences made of the symbols 1 and 2.
Assign each such sequence weight $w^a x^b$,
where $a$ is the number of 1's and $b$ is the length of the sequence.
Define the two-variable generating function $F(w,x)$
as the sum of the weights of all finite sequences
(including the empty sequence, whose weight is of course 1).
Let $c_n$ be the number of sequences of length $n$,
and $d_n$ be the number of 1's jointly contained in all those sequences
(so that $c_0=1$, $c_1=2$, $c_2=4$,
$d_0=0$, $d_1=1$, $d_2=4$).
\begin{itemize}
\item[(a)]
(10 points) Express $F(w,x)$ as a rational function
in the variables $w$ and $x$.
\item[(b)]
(10 points) Express the single-variable generating functions
$\sum_{n \geq 0} c_n x^n$ and $\sum_{n \geq 0} d_n x^n$
as rational functions in the variable $x$.
\item[(c)]
(10 points) Give exact formulas for $c_n$ and $d_n$.
\item[(d)]
(10 points) Compute $d_n/c_n$, and explain why your answer makes sense.
\end{itemize}
\item %3
(10 points) Let $F_n$ be the $n$th Fibonacci number
as Wilf indexes them (with $F_0=F_1=1$, $F_2=2$, etc.).
Find the lowest-degree non-trivial recurrence relation
satisfied by the sequence whose $n$th term is $F_n^2$,
and show that the sequence is not governed by any
non-trivial recurrence relation of lower degree.
(Here ``recurrence relation'' means
``homogeneous linear recurrence relation with constant coefficients''.)
\item %4
(10 points) Let $f_n$ be the $n$th Fibonacci number, indexed so that
$f_1=f_2=1$, $f_3=2$, etc.
Let $$g_n = \left\{ \begin{array}{ll}
1 & \mbox{if $n=0$,} \\
2f_n & \mbox{if $n>0$.} \end{array} \right.$$
Use generating functions to show that for all $n>0$,
$$\sum_{k=0}^n \, (-1)^k g_k g_{n-k} = 0.$$
\end{enumerate}
\bigskip
\noindent
{\sc Note:}
\medskip
\noindent
Where a problem asks for a formula, a (non-recursive)
closed-form expression is desired.
\bigskip
\begin{center}
(more)
\end{center}
\pagebreak
\noindent
In each case, full credit will be given
only if you offer a proof
(in the sense of an argument
that would convince an intelligent skeptic);
empirical reasoning
(showing that patterns are amply supported by data)
will get you only partial credit.
\medskip
\noindent
You may use a computer to do any of the steps,
but you should send a copy of your code to
{\tt propp@math.wisc.edu}.
\medskip
\noindent
You may use your notes from the class
(including homework solutions)
and all assigned or recommended texts.
Other sources of information are not permitted.
You should not discuss the test with anyone else,
except that you may (and indeed should!)\ contact Prof.\ Propp
if you are unsure
how a question is to be interpreted
or what sort of answer is being sought.
\end{document}