\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#21: Solutions
\end{center}
\medskip

\begin{enumerate}

\item
{\it 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.}

We may separate the case of $n$ odd and $n$ even, e.g.\ using 
$$A(n)=\frac12 \left((1+(-1)^n)A_{\mbox{even}}(n)
+(1-(-1)^n)A_{\mbox{odd}}(n)\right).$$

First take $n$ to be even, 
so that we may write $n=2m$.
When $m$ and $n$ are positive,
$A(n) = 2^m+2^{m+1}+\dots+2^{2m} = 2^{2m+1}-2^m$.
To check that this is consistent with Ehrhart reciprocity,
note that if $m$ and $n$ are negative
(say with $m=-M$ and $n=-N$),
$-2^{n+1}-2^{n+2}-\dots-2^{m-1} =
-(2^{1-N}+2^{2-N}+\dots+2^{-1-M}) =
-2^{1-N}(2^0+2^1+\dots+2^{M-2}) =
-2^{1-N}(2^{M-1}-1) =
-2^{1+2m}(2^{-1-m}-1) =
-2^m+2^{1+2m}$, which equals
$2^{2m+1}-2^m$ as predicted.

Next take $n$ to be odd, 
so that we may write $n=2m-1$.
When $m$ and $n$ are positive,
$A(n) = 2^m+2^{m+1}+\dots+2^{2m-1} = 2^{2m}-2^m$.
To check that this is consistent with Ehrhart reciprocity,
note that if $m$ and $n$ are non-positive
(say with $m=-M$ and $n=-N$),
$-2^{n+1}-2^{n+2}-\dots-2^{m-1} =
-(2^{1-N}+2^{2-N}+\dots+2^{-1-M}) =
-2^{1-N}(2^0+2^1+\dots+2^{M-1}) =
-2^{1-N}(2^M-1) =
-2^{2m}(2^{-m}-1) =
-2^{m}+2^{2m}$, which equals
$2^{2m}-2^m$ as predicted.

\item
{\it 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.}

$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) .
\]
The characteristic polynomial of this matrix is
$t^4-4t^3+3t^2+2t-1$.
By the Cayley-Hamilton Theorem,
$M^4-4M^3+3M^2+2M-I$ is the zero-matrix,
and more generally,
$M^n-4M^{n-1}+3M^{n-2}+2M^{n-3}-M^{n-4}=0$ for any $n \geq 4$.
Since $f(n)$ is the upper left entry of $M^n$,
we have $f(n)-4f(n-1)+3f(n-2)+2f(n-3)-f(n-4)=0$ for all $n \geq 4$,
which is the desired recurrence equation.

Since the matrix $M$ is invertible,
$M^n$ is defined for all integers $n$ (positive or negative),
and it follows from the Cayley-Hamilton theorem (as above) that in fact
$M^n-4M^{n-1}+3M^{n-2}+2M^{n-3}-M^{n-4}=0$ for any integer $n$.
Therefore, if we define $f(n)$ for all integers $n$ 
as the upper-left entry of $M^n$,
the bilateral sequence $\dots,f(n),\dots$
will satisfy the linear recurrence equation
$f(n)-4f(n-1)+3f(n-2)+2f(n-3)-f(n-4)=0$ for all integers $n$.
Hence we have found ``the'' extension of our original sequence
$f(1),f(2),\dots$ into the negative domain:
$f(-1)=1$,
$f(-2)=3$,
$f(-3)=6$,
$f(-4)=18$,
etc.

It only remains to interpret 
$f(-1), f(-2), f(-3),\dots$ combinatorially.
To this end, note that $M^{-1}$ is the matrix
\[
\left( \begin{array}{rrrr}
	 1 &  0 & -1 &  1 \\
	 0 &  0 &  1 & -1 \\
	-1 &  1 &  0 &  0 \\
	 1 & -1 &  0 &  1 
\end{array} \right) .
\]
The fact that the non-zero entries of $M^{-1}$ are all $\pm 1$
(and that $(M^{-1})_{i,j}$ is $-1$ precisely when $i$ and $j$ differ by 2)
gives us a combinatorial interpretation 
of the upper left entry of $M^{-n}=(M^{-1})^n$
as a signed enumeration of sequences.
Specifically, consider sequences 
consisting of 1's, 2's, 3's, and 4's, such that: 
a 1 cannot be followed by a 2;
a 2 cannot be followed by a 1 or a 2;
a 3 cannot be followed by a 3 or a 4;
and a 4 cannot be followed by a 3.
Call such a sequence ``okay'',
and define the sign of an okay sequence to be $+1$ or $-1$
according to whether the number of pairs of consecutive terms
that differ by exactly 2 is even or odd.
Then the upper left entry of $(M^{-1})^n$
is equal to the sum of the signs of the okay sequences of length $n+1$
whose first and last terms both equal 1.

However, we can do better, if we notice
that all the okay sequences of length $n+1$ have the same sign
(so that there is no cancellation),
and that, indeed, the okay sequences that begin and end with a 1
all have sign $+1$.
For, if we divide $\{1,2,3,4\}$ into
$\{1,4\}$ and $\{2,3\}$ 
(the ``outer values'' and ``inner values'' respectively),
we can check that the only way in which an inner value in an okay sequence
can be followed by an outer value (or vice versa)
is if the two values differ by 2.
Thus, in counting pairs of consecutive terms that differ by 2,
we are counting the number of times we move
from an inner value to an outer value or vice versa.
But since we both begin and end with an outer value (namely 1),
the number of such transitions must be even.
This proves that every okay sequence whose first and last term is 1
must have sign $+1$, and it follows that
$f(-n)$ can be interpreted more simply as
the number of okay sequences of length $n+1$
whose first and last terms both equal 1.

\end{enumerate}

\end{document}
