\documentclass[12pt]{article}
\pagestyle{empty}
\begin{document}
\large
\begin{center}
Math 491, Take-home Midterm \\
\end{center}
\medskip
{\it Do all of the following problems:}
\begin{itemize}
\item[1(a)]
(20 points) {\it 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$.}
\medskip
First solution: There are three possibilities for each column:
a penny in the Top cell,
a penny in the Bottom cell,
or a penny in Neither cell.
A permitted configuration of pennies
can be represented as a sequence of T's, B's, and N's
such that no two T's occur in a row
and no two B's occur in a row.
The number of such sequences is the sum of the entries
in the $n-1$st power of the transfer matrix
\[ \left(
\begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{array}
\right) \]
The characteristic polynomial of this matrix is
$t^3 - t^2 - 3t - 1 = (t+1)(t^2-2t-1)$
with roots $-1,1+\sqrt{2},1-\sqrt{2}$.
Thus the final answer is of the form
$a_n = A(-1)^n+B(1+\sqrt{2})^n+C(1-\sqrt{2})^n$
for suitable constants $A$, $B$, and $C$.
To find $A$, $B$, and $C$, use the fact that
$a_1 = 3$, $a_2 = 7$, and $a_3 = 17$
to get
$A = 0$, $B = \frac12\sqrt{2}+\frac12$, and $C = \frac12-\frac12\sqrt{2}$.
Multiplying the generating function $3x+7x^2+17x^3+41x^4+99x^5+\dots$
by $1-x-3x^2-x^3$, we get $3x+4x^2+x^3+0x^4+0x^5+\dots$.
So $$\sum_{n \geq 1} a_n x^n = \frac{3x+4x^2+x^3}{1-x-3x^2-x^3}
= \frac{3x+x^2}{1-2x-x^2}.$$
\smallskip
Second solution: Like the above, but we include $n=0$
until the very end.
The characteric polynomial $t^3 - t^2 - 3t - 1$
tells us that the $a_n$'s satisfy the recurrence
$a_{n+3} - a_{n+2} - 3a_{n+1} - a_n = 0$,
which (with $n=0$) gives us $a_0 = 1$
as the correct value to use.
Then we can solve for $A$, $B$, and $C$
using the fact that $a_0 = 1$, $a_1 = 3$, and $a_2 = 7$
(which involves slightly less arithmetic than the first solution).
Multiplying the generating function $1+3x+7x^2+17x^3+41x^4+99x^5+\dots$
by $1-x-3x^2-x^3$, we get $1+2x+0x^2+0x^3+\dots$.
So
\[ \sum_{n \geq 0} a_n x^n = \frac{1+2x+x^2}{1-x-3x^2-x^3} \]
and
\begin{eqnarray*}
\sum_{n \geq 1} a_n x^n & = & \frac{1+2x+x^2}{1-x-3x^2-x^3} - 1 \\
& = & \frac{1+x}{1-2x-x^2} - 1 \\
& = & \frac{3x+x^2}{1-2x-x^2}.
\end{eqnarray*}
\smallskip
Third solution: Let $A(x)$ be the generating function for
configurations of width 1 or greater
in which every column has at least one penny,
and $B(x)$ be the generating function for
configurations of width 1 or greater
in which every column has no pennies.
Then the desired generating function is
$A(x)+B(x)+A(x)B(x)+B(x)A(x)+A(x)B(x)A(x)+B(x)A(x)B(x)+\dots$,
since every non-empty permitted configuration of pennies
consists of alternating blocks
of the two different kinds.
Let's omit ``$(x)$'' for convenience.
Then we can write the infinite sum
$A+B+AB+BA+ABA+BAB+\dots$
as
$A+ABA+ABABA+\dots+BA+BABABA+\dots
+B+BAB+BABAB+\dots+AB+ABABAB+\dots
=(A+BA)/(1-BA)+(B+AB)/(1-AB)
=(A+B+2AB)/(1-AB)$.
It is easy to see that $A=A(x)=2x+2x^2+2x^3+\dots=\frac{2x}{1-x}$
and $B=B(x)=x+x^2+x^3+\dots=\frac{x}{1-x}$.
So
\begin{eqnarray*}
\frac{A+B+2AB}{1-AB}
& = & \frac{\frac{3x}{1-x}+\frac{4x^2}{(1-x)^2}}{1-\frac{2x^2}{(1-x)^2}} \\
& = & \frac{3x(1-x)+4x^2}{1-2x+x^2-2x^2} \\
& = & \frac{3x+x^2}{1-2x-x^2}.
\end{eqnarray*}
\medskip
\item[1(b)]
(20 points) {\it 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$.}
\medskip
First solution: We can think of these cylindrical configurations of length $n$
as being ordinary configurations of length $n+1$
with the property that the first and last symbols agree.
Hence the number of such configurations is the sum of the diagonal entries
in the $n$th power of the 3-by-3 matrix introduced for part (a).
As in part (a), the fact that the characteristic polynomial is $t^3-t^2-3t-1$
tells us that we can use $1-x-3x^2-x^3$ as our denominator.
Multiplying the generating function $7x^2+13x^3+35x^4+81x^5+199x^6\dots$
by $1-x-3x^2-x^3$, we get $7x^2+6x^3+x^4+0x^5+0x^6+\dots$,
so $\sum_{n \geq 2} b_n x^n = \frac{7x^2+6x^3+x^4}{1-x-3x^2-x^3}$.
\smallskip
Second solution: Like the first, but we include the term $b_1 = 1 =$
the trace of the 3-by-3 matrix $M$. Then as discussed in class we have
$\sum_{n \geq 1} b_n x^n = \sum_{n \geq 1} {\rm Trace}(M^n) x^n
=\frac{-xQ'(x)}{Q(x)}$
with $Q(x) = \det(I-xM) = 1-x-3x^2-x^3$, so
$\sum_{n \geq 1} b_n x^n = \frac{x+6x^2+3x^3}{1-x-3x^2-x^3}$
and
$\sum_{n \geq 2} b_n x^n = \frac{x+6x^2+3x^3}{1-x-3x^2-x^3} - x
= \frac{7x^2+6x^3+x^4}{1-x-3x^2-x^3}$.
\medskip
\item[2(a)]
(20 points) {\it For all $n \geq 0$,
let $c_n$ be the number of sequences of length $n$
in which every term is 1, 2, 3, or 4,
such that a 1 or a 4 never appears immediately after a 1 or a 2.
Express the generating function
$\sum_{n \geq 0} c_n x^n = 1 + 4x + 12x^2 + 36x^3 + \dots$
as a rational function of $x$,
and give an algebraic formula for $c_n$ valid for all $n \geq 0$.}
\medskip
First solution:
The matrix expressing the adjacency constraints is
\[ M = \left( \begin{array}{cccc}
0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{array} \right) \]
with characteristic polynomial $t^4-3t^3$;
the roots are 0, 0, 0, and 3.
The answer we seek is therefore of the form
$(c_0,c_1,c_2,c_3,\dots) = (A,B,C,0,0,0,\dots) + D(1,3,9,27,81,\dots)$.
Since
\[ M^2 = \left( \begin{array}{cccc}
1 & 2 & 2 & 1 \\
1 & 2 & 2 & 1 \\
2 & 4 & 4 & 2 \\
2 & 4 & 4 & 2
\end{array} \right) , \]
we have $27D = c_3 = $ sum of entries of $M^2 = 36$, so $D=4/3$.
Hence
$(c_0,c_1,c_2,c_3,\dots) =
(-1/3,0,0,0,0,0,\dots) + (4/3,4,12,36,108,324,\dots)$.
We can write the $n$th term as $c_n = \frac43 3^n - \frac13 0^n$.
Multiplying $1+4x+12x^2+36x^2+108x^3+\dots$ by $1-3x$
we get $1+x+0x^2+0x^3+\dots$,
so the generating function is $\frac{1+x}{1-3x}$.
\smallskip
Second solution:
The number of permitted sequences of length $n \geq 2$
is given by the sole entry of $u M^{n-1} v$
where $u$ is the all-1's row-vector of length 4
and $v$ is the all-1's column-vector of length 4.
Thus the generating function for all permitted sequences of length $\geq 2$
is
$u \, (M x^2 + M^2 x^3 + M^3 x^4 + \dots) \, v \,
= \, u \, Mx^2 \, (I - Mx)^{-1} \, v$.
So we ask Maple to set
\begin{verbatim}
u := matrix(1,4,[1,1,1,1]);
v := matrix(4,1,[1,1,1,1]);
M := matrix(4,4,[0,1,1,0,0,1,1,0,
1,1,1,1,1,1,1,1]);
\end{verbatim}
and to calculate
\begin{verbatim}
simplify(multiply(u,evalm(M*x^2*(1-M*x)^(-1)),v));
\end{verbatim}
we get as the answer the 1-by-1 matrix whose sole entry is
$12x^2/(1-3x)$.
To get the correct constant term and linear term,
we must add $1+4x$, obtaining
$1 + 4x + 12x^2/(1-3x) = (1+x)/(1-3x)$.
Note that you probably wouldn't want to do the problem
this way by hand, since the matrix-calculations are rather messy;
indeed, if instead of
\begin{verbatim}
simplify(multiply(u,evalm(M*x^2*(1-M*x)^(-1)),v))
\end{verbatim}
we'd given the command
\begin{verbatim}
multiply(u,evalm(M*x^2*(1-M*x)^(-1)),v)
\end{verbatim}
we would have seen the rather daunting expression
\begin{verbatim}
matrix([[4*x^2*(-x^2/(-1+3*x)+x*(-1+x)/(-1+3*x))
+2*x^2*(-(1-3*x+x^2)/(-1+3*x)-x^2/(-1+3*x)
+2*x*(-1+x)/(-1+3*x))+2*x^2*((x^2+2*x-1)/(-1+3*x)
-x*(x+1)/(-1+3*x))+2*x^2*(x*(-1+x)/(-1+3*x)
+(x^2+2*x-1)/(-1+3*x)-2*x*(x+1)/(-1+3*x))
+2*x^2*(x*(-1+x)/(-1+3*x)-(x^2-2*x+1)/(-1+3*x))
+2*x^2*(2*x*(-1+x)/(-1+3*x)-(x^2-2*x+1)/(-1+3*x)
-x*(x+1)/(-1+3*x)) +2*x^2*(-2*x^2/(-1+3*x)
+x*(-1+x)/(-1+3*x)+(x^2+2*x-1)/(-1+3*x))]])
\end{verbatim}
Fortunately, Maple is fairly adept at cleaning up such messes.
\medskip
\item[2(b)]
(20 points) {\it Let $d_n$ be the total number of 1's
that occur in all such sequences,
so that $d_n/c_n$ is the average number of 1's per sequence,
and $d_n/nc_n$ is the proportion of terms of each sequence equal to 1
(on average).
The values $d_1=1$, $d_2=4$, and $d_3=16$
will help you verify that you have
understood the general definition of $d_n$.
Find a linear recurrence relation satisfied by $d_n$,
an exact formula for $d_n/c_n$,
and the limit of $d_n/nc_n$ as $n$ goes to infinity.
(Hint: This limit is a rational number.)}
\medskip
First solution:
For $i=1$ through 4,
define $c_i(n)$ as the number of permitted sequences of length $n$
whose last symbol is $i$.
Note that for all $n \geq 2$,
$c_i(n)$ is equal to $(2)(3)^{n-2}$
if $i$ is 1 or 4,
and is equal to $(4)(3)^{n-2}$
if $i$ is 2 or 3.
It's easy to guess this pattern if we just try
taking powers of $M$,
and once we've guessed the pattern,
it's easy to prove it by induction:
since $( \ 1 \ 2 \ 2 \ 1 \ )$ times $M$ equals
$( \ 3 \ 6 \ 6 \ 3 \ )$, it follows that
$( \ (2)(3)^{n-2} \ (4)(3)^{n-2} \ (4)(3)^{n-2} \ (2)(3)^{n-2} \ )$
times $M$ equals
$( \ (2)(3)^{n-1} \ (4)(3)^{n-1} \ (4)(3)^{n-1} \ (2)(3)^{n-1} \ )$.
From this, we can derive joint non-homogeneous recurrence relations
for $d_1(n)$, $d_2(n)$, $d_3(n)$, and $d_4(n)$,
where $d_i(n)$ is defined as the total number of 1's
that occur in all permitted sequences that end with $i$.
Each of the sequences of length $n$ that end in 1
can be followed by a 2 or a 3,
so that all such sequences
jointly contribute the amount $d_1(n)$ towards $d_2(n+1)$ and $d_3(n+1)$.
Likewise, the sequences of length $n$ that end in a 2
jointly contribute the amount $d_2(n)$ towards $d_2(n+1)$ and $d_3(n+1)$.
Similarly for sequences ending in a 3 and sequences ending in a 4.
But these sequences also contribute to $d_1(n+1)$ and $d_4(n+1)$.
Specifically, the sequences of length $n$ that ends in a 3
contribute $d_3(n)+c_3(n)$ to $d_1(n+1)$
and $d_3(n)$ to $d_4(n+1)$.
(The reason for the extra term $c_3(n)$
is that when we add a 1 at the end of
each of the $c_3(n)$ sequences of length $n$ ending with a 3,
we get to contribute all the $d_3(n)$ 1's that the old sequences had,
plus $c_3(n)$ new 1's, namely the ones that just got added on at the end.)
Likewise for the sequences of length $n$ that end in a 4.
Hence
\begin{eqnarray*}
d_1(n+1) & = & d_3(n)+c_3(n)+d_4(n)+c_4(n) \\
d_2(n+1) & = & d_1(n)+d_2(n)+d_3(n)+d_4(n) \\
d_3(n+1) & = & d_1(n)+d_2(n)+d_3(n)+d_4(n) \\
d_4(n+1) & = & d_3(n)+d_4(n).
\end{eqnarray*}
This recurrence
(which holds for all $n \geq 1$)
suffices to determine the $d_i(n)$'s by recursion,
if we impose the appropriate initial conditions
$d_1(1) = 1$, $d_2(1) = d_3(1) = d_4(1) = 0$
and recall that $c_2(n) = c_3(n) = (4)(3)^{n-2}$.
Note that $d_2(n) = d_3(n)$ for all $n \geq 2$,
since the right-hand sides of the 2nd and 3rd equations agree.
Moreover, this holds for $n = 1$ as well.
Hence we can omit $d_3(n)$ from the system,
replacing it where it appears by $d_2(n)$:
\begin{eqnarray*}
d_1(n+1) & = & d_2(n)+c_2(n)+d_4(n)+c_4(n) \\
d_2(n+1) & = & d_1(n)+2d_2(n)+d_4(n) \\
d_4(n+1) & = & d_2(n)+d_4(n).
\end{eqnarray*}
(Here we also use $c_3(n)=c_2(n)$.)
We can turn this into a homogeneous system
if we include $c_2$ and $c_4$ in the recurrence,
via the equations $c_2(n+1) = 3c_2(n)$ and $c_4(n+1) = 3c_4(n)$.
Then we get
\[ \left( \begin{array}{c}
d_1(n+1) \\
d_2(n+1) \\
d_4(n+1) \\
c_2(n+1) \\
c_4(n+1) \end{array} \right) =
\left( \begin{array}{cccccc}
0 & 1 & 1 & 1 & 1 \\
1 & 2 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 3 & 0 \\
0 & 0 & 0 & 0 & 3 \end{array} \right)
\left( \begin{array}{c}
d_1(n) \\
d_2(n) \\
d_4(n) \\
c_2(n) \\
c_4(n) \end{array} \right) \]
All four quantities, and linear combinations thereof,
satisfy the recurrence relation associated with
the characteristic polynomial of this matrix.
Note that $d_n = d_1(n) + d_2(n) + d_3(n) + d_4(n)
= d_1(n) + 2d_2(n) + d_4(n)$
is such a linear combination.
Since the characteristic polynomial of the 5-by-5 matrix is
$t^5 - 9t^4 + 27t^3 - 27t^2 = t^2 (t-3)^3$,
we see that $d_n$ satisfies the recurrence
$d_{n+5} - 9d_{n+4} + 27d_{n+3} - 27d_{n+2} = 0$.
And this would in fact be an acceptable answer.
(Note that this is equivalent to saying that
$T^2 (T-3I)^3$ annihilates the sequence $(d_0,d_1,d_2,\dots)$.)
However, by finding a formula for $d_n$,
we'll find that there's a simpler recurrence that applies.
Since the characteristic polynomial
has roots 0, 0, 3, 3, and 3,
we can write $d_n$ as $A \cdot 3^n + B \cdot n 3^n + C \cdot n^2 3^n$
for all $n \geq 2$.
Using the specific values $d_2=4$ and $d_3=16$ and $d_4 = 60$,
we find $A=B=\frac{4}{27}$ and $C=0$,
so $d_n = \frac{4}{27}(n+1)3^n$ for $n \geq 2$.
Since there is no $n^2 3^n$ contribution,
we see that
$T^2 (T-3I)^2$ annihilates $(d_0,d_1,d_2,\dots)$,
so that $d_n$ satisfies the recurrence
$d_{n+4} - 6 d_{n+3} + 9 d_{n+2} = 0$.
Since for $n \geq 2$ we have $c_n = \frac{4}{3} 3^n$
and $d_n = \frac{4}{27}(n+1) 3^n$,
we have $d_n/c_n = \frac{1}{9} (n+1)$
(with $d_1/c_1 = 1/4$).
So $d_n/nc_n = \frac{n+1}{9n}$,
which converges to $\frac{1}{9}$ as $n$ gets large.
\smallskip
Second solution:
Here's a partial-credit sort of approach to the problem.
Say we succeed in obtaining the numbers $d_n$ for $2 \leq n \leq 8$
by writing a computer program
that exhaustively goes through all possibilities:
4, 16, 60, 216, 756, 2592, and 8748.
We note that each term is roughly three times the preceding one,
so we write down values of $d_{n+1} - 3d_n$,
obtaining the sequence 4, 12, 36, 108, 324, 972.
Now we notice that each term is exactly three times the preceding one.
We can conjecture that this is true for all applicable values of $n$;
that is $d_{n+2} - 3d_{n+1} = 3(d_{n+1} - d_{n})$ for all $n \geq 2$.
That is, we conjecture that the sequence $(d_2,d_3,d_4,\dots)$
is annihilated by the linear operator $(T-3I)^2$.
But $(d_2,d_3,d_4,\dots)$ is just $T^2$ applied to
$(d_0,d_1,d_2,d_3,d_4,\dots)$.
So we are conjecturing that $T^2 (T-3I)^2$ annihilates $(d_0,d_1,d_2,\dots)$.
Since $T^2 (T-3I)^2 = T^4 - 6 T^3 + 9 T^2$,
we thus conjecture that
$d_{n+4} = 6 d_{n+3} - 9 d_{n+2}$
for all $n \geq 0$.
\smallskip
Third solution:
Adopting the method of the second solution to part (a),
we create a two-variable generating function $F(w,x)$;
each permitted sequence has weight $w^a x^b$,
where $a$ is the total number of 1's in the sequence
and $b$ is the total length of the sequence
(which we assume is at least 2).
This generating function is
$u \, (M x^2 + M^2 x^3 + M^3 x^4 + \dots) \, v \,
= \, u \, Mx^2 \, (I - Mx)^{-1} \, v$
where now
\[ u = \left( \begin{array}{cccc} w & 1 & 1 & 1 \end{array} \right) ,\]
\[ v = \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array} \right) ,\]
and
\[ M = \left( \begin{array}{cccc}
0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
w & 1 & 1 & 1 \\
w & 1 & 1 & 1 \end{array} \right) .\]
(It makes sense that the row-vector $u$ has a $w$ in its first component:
we should pick up a factor of $w$ in the weight of a word
if the first symbol is a 1.
Likewise, it makes sense that $M$ has $w$'s in its first column,
since that corresponds to adding a new 1 at the end of the growing word,
which increases its weight by $w$.
On the other hand, it also makes sense that there are no $w$'s in
the column-vector $v$,
since multiplying by $v$ is just a handy way for summing up the entries
of the row-vector that results
from multiplying together all the earlier factors.)
So we tell Maple
\begin{verbatim}
u := matrix(1,4,[w,1,1,1]);
v := matrix(4,1,[1,1,1,1]);
M := matrix(4,4,[0,1,1,0,0,1,1,0,w,1,1,1,w,1,1,1]);
F := simplify(multiply(
u,evalm(M*x^2*(1-M*x)^(-1)),v))[1,1];
\end{verbatim}
and we find that
$F(w,x) = x^2 ( w^2 x + 2wx + 4w - 3x + 8) / (1 - 3x + x^2 - x^2 w)$.
Now we want to differentiate with respect to $w$
and set $w=1$, which Maple is happy to do:
{\tt simplify(subs(w=1,diff(F,w)));} elicits the reply
$4x^2(1-2x)/(1-3x)^2$.
So this is the generating function for $d_n$.
Since the denominator is $1-6x+9x^2$,
the sequence $d_n$ eventually satisfies the second-order recurrence
$d_{n+2} = 6d_{n+1} + 9d_{n}$;
but since the numerator does not have degree $2-1=1$ as we would like
but rather exceeds this degree by 2,
the recurrence relation won't kick in until $n=2$.
We proceed from here as in the first solution.
\medskip
\item[(2)] (revised)
{\it 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$).}
\medskip
\item[2(a)]
(10 points) {\it Express $F(w,x)$ as a rational function
in the variables $w$ and $x$.}
\medskip
First solution:
Write $F(w,x) = p_0 (w) + p_1 (w) x + p_2 (w) x^2 + \dots$.
Since every sequence of 1's and 2's can be extended in two
different ways, namely by adding a 1 at the end
(which multiplies its weight by $wx$)
or by adding a 2 at the end
(which multiplies its weight by $x$),
we have $p_{k+1} (w) = (1+w)p_k$.
So, starting from $p_0(w) = 1$,
we get $p_1(w) = 1+w$,
$p_2(w) = (1+w)^2$,
and in general, $p_k(w) = (1+w)^k$.
So $F(w,x) = 1 + (1+w)x + (1+w)^2 x^2 + \dots$,
a geometric series with sum $1/(1-(1+w)x) = 1/(1-x-wx)$.
\smallskip
Second solution:
We adopt the method of the third solution to the original problem.
The sum of the weights of all the words of length $\geq 1$ is
$1 \, + \, u \, (x + M x^2 + M^2 x^3 + M^3 x^4 + \dots) \, v \,
= \, u \, x \, (I - Mx)^{-1} \, v$
where
\[ u = \left( \begin{array}{cccc} w & 1 \end{array} \right) ,\]
\[ v = \left( \begin{array}{c} 1 \\ 1 \end{array} \right) ,\]
and
\[ M = \left( \begin{array}{cccc}
w & 1 \\
w & 1 \end{array} \right) .\]
We find that
$u x (I - Mx)^{-1} v$
is equal to $\frac{1}{1-x-wx}$.
\medskip
\item[2(b)]
(10 points) {\it 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$.}
\medskip
Solution: For the former, we specialize $F(w,x)$ by setting $w=1$:
$\sum_{n \geq 0} c_n x^n = 1/(1-x-x) = 1/(1-2x)$.
For the latter, we differentiate with respect to $w$
and then set $w=1$:
$\frac{d}{dw} 1/(1-x-wx) = x/(1-x-wx)^2$, so
$\sum_{n \geq 0} d_n x^n = x/(1-x-x) = x/(1-2x)^2$.
\medskip
\item[2(c)]
(10 points) {\it Give exact formulas for $c_n$ and $d_n$.}
\medskip
$1/(1-2x)
= 1 + (2x) + (2x)^2 + (2x)^3 + \dots
= 1 + (2)x + (2^2) x^2 + (2^3) x^3 + \dots$,
so $c_n = $ coefficient of $x^n$ $= 2^n$.
This makes sense, since of course the number of sequences of length $n$
composed of 1's and 2's is $2^n$.
$x/(1-2x)^2 = x(1 + (2)x + (2^2) x^2 + (2^3) x^3 + \dots)
= x(1 + 2(2)x + 3(2^2)x^2 + 4(2^3)x^3 + \dots)
= x + 2(2)x^2 + 3(2^2)x^3 + 4(2^3)x^4 + \dots$,
so $d_n = $ coefficient of $x^n$ $= n(2^{n-1})$.
This makes sense, since the $2^n$ sequences of length $n$
jointly contain $n2^n$ digits,
of which exactly half are 1's and the other half are 2's
(since the conditions of the problem are symmetrical
between 1 and 2).
\medskip
\item[2(d)]
(10 points) {\it Compute $d_n/c_n$, and explain why your answer makes sense.}
\medskip
We get $d_n/c_n = n/2$,
and $d_n/nc_n = 1/2$ for all $n$.
As remarked in part (c), this makes sense;
half of the symbols should be 1's and half should be 2's.
\medskip
\item[3]
(10 points) {\it 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''.)}
\medskip
We have $F_n = Ar^n + Bs^n$
with $r=(1+\sqrt{5})/2$
and $s=(1-\sqrt{5})/2$,
with $A,B$ non-zero.
Hence $F_n^2 = A^2 (r^2)^n + 2AB (rs)^n + B^2 (s^2)^n$,
which is a linear combination of the building blocks
$(r^2)^n$, $(rs)^n$, and $(s^2)^n$.
Hence the sequence $(F_0^2, F_1^2, F_2^2, F_3^2, \dots)$
is annihilated by the operator
$(T-r^2I)(T-rsI)(T-s^2I)$.
We have $rs = \frac{1+\sqrt{5}}{2} \frac{1-\sqrt{5}}{2} = \frac{1-5}{4} = -1$,
so $(T-rsI) = (T+I)$.
As for the other two factors in the operator,
$r^2 = \frac{6+2\sqrt{5}}{4} = \frac{3+\sqrt{5}}{2}$,
$s^2 = \frac{3-\sqrt{5}}{2}$,
$r^2 + s^2 = \frac{3+3}{2} = 3$,
and $r^2 s^2 = \frac{9-5}{4} = 1$,
so $(T-r^2I)(T+r^2I) = T^2 - 3T + I$.
Hence
$(T-r^2I)(T-rsI)(T-s^2I) = (T + I)(T^2 - 3T + I) = T^3 - 2T^2 -2T + I$
annihilates the sequence whose $n$th term is $F_n^2$.
It follows that
$F_{n+3}^2 - 2F_{n+2}^2 - 2F_{n+1}^2 + F_{n}^2 = 0$,
i.e.,
$F_{n+3}^2 = 2F_{n+2}^2 + 2F_{n+1}^2 - F_{n}^2$,
for all $n \geq 0$.
Check: $3^2 = 2(2^2) + 2(1^2) - 1^2$,
$5^2 = 2(3^2) + 2(2^2) - 1^2$,
$8^2 = 2(5^2) + 2(3^2) - 2^2$,
$13^2 = 2(8^2) + 2(5^2) - 3^2$,
etc.
So the sequence satisfies a recurrence of degree 3.
To finish the problem,
suppose there existed coefficients $A$ and $B$
such that
$F_{n+2}^2 = AF_{n+1}^2 + BF_{n}^2$ for all $n \geq 0$.
Then, plugging in $n=0$ and $n=1$, we get
$2^2 = 1^2 A + 1^2 B$
and
$3^2 = 2^2 A + 1^2 B$,
i.e.,
$4 = A+B$ and $9=4A+B$.
Solving, we get $A=5/3$ and $B=7/3$.
But this would give
$F_4^2 = (5/3) F_3^2 + (7/3) F_2^2 = (5/3) 3^2 + (7/3) 2^2$
(which is not even an integer),
in contrast to the fact that $F_4^2 = 5^2 = 25$.
Alternatively, you could try to find $A,B,C$
so as to satisfy $F_{n+2}^2 = AF_{n+1}^2 + BF_{n}^2$
for $n$ equal to 0, 1, or 2;
then you would find that the only possible solution is
$A=B=C=0$,
which does not correspond to a recurrence relation for the sequence.
\medskip
\item[4]
(10 points) {\it 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.$$}
\medskip
The alternating sum $\sum_{k=0}^n \, (-1)^k g_k g_{n-k}$
should remind us of things like
${n \choose 0}^2 - {n \choose 1}^2 + {n \choose 2}^2 - {n \choose 3}^2 +\dots$
from the beginning of the term,
and we can apply the same method as we did then.
In fact, it is easy to check that
$g_0 g_n - g_1 g_{n-1} + g_2 g_{n-2} - \dots$
is equal to the coefficient of $x^n$
in the product
$(g_0 - g_1 x + g_2 x^2 - \dots)
(g_0 + g_1 x + g_2 x^2 + \dots)$.
If you weren't able to see this straight away,
you might still have figured it out
by applying Wilf's general tactic
of multiplying by $x^n$ and summing.
$\sum_{n \geq 0} \sum_{k=0}^n \, (-1)^k g_k g_{n-k} x^n$
can be rewritten as
$$\sum_{n \geq 0} \sum_{k=0}^n \, (-1)^k g_k x^k g_{n-k} x^{n-k}$$
which is equal to
$$\sum_{n \geq 0} \sum_{k=0}^n \, (g_k (-x)^k) (g_{n-k} x^{n-k}).$$
If we re-index by setting $j=n-k$, we get
$\sum_{j,k \geq 0} \, (g_k (-x)^k) (g_j x^j)$,
which factors as
$\sum_{j \geq 0} \, (g_j x^j)$
times
$\sum_{k \geq 0} \, (g_k (-x)^k)$,
or (renaming our indices)
$\sum_{n \geq 0} \, (g_n x^n)$
times
$\sum_{n \geq 0} \, (g_n (-x)^n)$.
We know that $\sum_{n \geq 1} f_n x^n = \frac{x}{1-x-x^2}$,
so $\sum_{n \geq 0} g_n x^n = 1 + 2 \frac{x}{1-x-x^2}
= \frac{(1-x-x^2)+2x}{1-x-x^2} = \frac{1+x-x^2}{1-x-x^2}$.
Replacing $x$ by $-x$, we get
$\sum_{n \geq 0} g_n (-x)^n = \frac{1+(-x)-(-x)^2}{1-(-x)-(-x)^2}
= \frac{1-x-x^2}{1+x-x^2}$.
Multiplying the two together, we get
$\frac{1+x-x^2}{1-x-x^2} \frac{1-x-x^2}{1+x-x^2}$,
which equals 1, i.e., $1+0x+0x^2+\dots$.
For all $n>0$, the coefficient of $x^n$ in $1+0x+0x^2+\dots$ is 0,
so we have proved the claim.
\end{itemize}
\end{document}