\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#21 \\
(due 12/13/01)
\end{center}
\medskip

\begin{enumerate}

\item
For $n \geq 0$
let $A(n) = \sum_{n/2 \leq k \leq n} 2^k$
(where the sum is only over integer values of $k$),
so that $A(0) = 1$, $A(1) = 2$, $A(2) = 6$, etc.
Extend $A(n)$ to the negative domain in two different ways, 
and check that they agree:
first, by finding a formula for $A(n)$ when $n$ is positive;
and second, by applying the polytope reciprocity theorem.

\item
For $n \geq 0$,
let $f(n)$ be the number of integer sequences of length $n+1$
consisting of 1's, 2's, 3's, and 4's,
such that the first term is 1, the last term is 1,
and any two consecutive terms differ by 0 or $\pm 1$.
Thus $f(0)=1$, $f(1)=1$, $f(2)=2$, $f(3)=4$, $f(4)=9$, etc.
Show that this sequence satisfies a linear recurrence
with constant coefficients,
so that $f(-1), f(-2), f(-3),\dots$ have natural values.
Interpret these values combinatorially.
%Hint: $f(n)$ is the upper left entry of $M^n$,
%where $M$ is the matrix
%\[
%\left( \begin{array}{cccc}
%	1 & 1 & 0 & 0 \\
%	1 & 1 & 1 & 0 \\
%	0 & 1 & 1 & 1 \\
%	0 & 0 & 1 & 1 
%\end{array} \right) .
%\]
%To interpret $f(-1)$, $f(-2)$, $f(-3)$, \dots,
%consider products of inverses of matrices of the form
%\[
%\left( \begin{array}{cccc}
%	a_i & a_i & 0   & 0   \\
%	b_i & b_i & b_i & 0   \\
%	0   & c_i & c_i & c_i \\
%	0   & 0   & d_i & d_i 
%\end{array} \right) .
%\]

\end{enumerate}

\end{document}
