\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 192r, Problem Set \#3: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it Let $F_n$ be the $n$th Fibonacci number,
as Wilf indexes them 
(with $F_0=F_1=1$, $F_2=2$, etc.).
Give a simple homogeneous linear recurrence relation
satisfied by the sequence whose $n$th term is...}
\begin{itemize}
\item[(a)] {\it $nF_n$:}

This sequence is given by a formula of the form $Anr^n+Bns^n$
(since $F_n = Ar^n+Bs^n$), where $r$ and $s$ are the roots
of $t^2-t-1=0$.
So we need a polynomial which has $r$ as a double root
and $s$ as a double root.
$(t^2-t-1)^2=t^4-2t^3-t^2+2t+1$ will certainly do.
So, writing the $n$th term of the given sequence as $f_n$,
we have $f_{n+4}=2f_{n+3}+f_{n+2}-2f_{n+1}-f_n$.

Alternatively, we can use generating functions:
If $F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \dots = 1/(1-x-x^2)$,
then, differentiating, we have
$1F_1 + 2F_2 x + 3F_3 x^2 + \dots = (1+2x)/(1-x-x^2)^2$,
and the occurrence of $(1-x-x^2)^2 = 1-2x-x^2+2x^3+x^4$ in the denominator
tells us that the sequence must satisfy the recurrence
$f_{n+4}=2f_{n+3}+f_{n+2}-2f_{n+1}-f_{n}$.

\item[(b)] {\it $1F_1+2F_2+...+nF_n$:}

If we apply the operator $T-I$ to this sequence,
we get the sequence considered in part (a).
So the sequence $f_n$ whose $n$th term is $1F_1+...+nF_n$
is annihilated by the operator
$(T-I)(T^4-2T^3-T^2+2T+I) = T^5-3T^4+T^3+3T^2-T-I$.

Alternatively, we can use generating functions,
and multiply the formal power series $(1+2x)/(1-x-x^2)^2$
(considered in the previous sub-problem)
by $1+x+x^2+\dots = 1/(1-x)$.
The coefficients of the resulting formal power series
are easily seen to be partial sums of exactly the desired kind.
So the new denominator is $(1-x)(1-x-x^2)^2=1-3x+x^2+3x^3-x^4-x^5$,
which tells us that the sequence must satisfy the recurrence
$f_{n+5}=3f_{n+4}-f_{n+3}-3f_{n+2}+f_{n+1}+f_n$.

\item[(c)] {\it $nF_1+(n-1)F_2+...+2F_{n-1}+F_n$:}
This sum is the coefficient of $x^n$
in the product of the formal power series 
$F_1 x + F_2 x^2 + ... + F_n x^n + ...$
with the formal power series 
$1 + 2x + 3x^2 + ... + nx^{n-1} + ...$.
The former is given by a formal power series with denominator $1-x-x^2$
and the latter is given by a formal power series with denominator $(1-x)^2$;
when we multiply them, we get a formal power series
with denominator $(1-x-x^2)(1-x)^2=1-3x+2x^2+x^3-x^4$,
so the sequence satisfies the recurrence
$f_{n+4}=3f_{n+3}-2f_{n+2}-f_{n+1}+f_n$.

\item[(d)] {\it $F_n$ when $n$ is odd, and $2^n$ when $n$ is even:}
We saw in class that the Fibonacci numbers
satisfy the recurrence $f_{n+4} = 3f_{n+2} - f_n$.
On the other hand, the powers of two
satisfy the recurrence $f_{n+2} = 4f_n$.
Since any multiple of $T^4-3T^2+I$ annihilates the former,
and any multiple of $T^2-4I$ annihilates the latter,
an operator that annihilates both sequences
(while only looking two, four, or six terms earlier)
is $(T^4-3T^2+I)(T^2-4I) = T^6 - 7T^4 + 13T^2 - 4I$.
So $f_{n+6}=7f_{n+4}-13f_{n+2}+4f_n$. 

\end{itemize}

\item
{\it The sequence of polynomials $f_n(x)$ in problem 2 of problem set 1 
satisfies a second-order linear recurrence relation
with coefficients that are Laurent polynomials in $x$.}

\begin{itemize}  
\item[(a)] {\it Find it, and prove that it is correct.}

We will prove that 
\begin{equation}
f_{n+1}=(2+1/x^2)f_{n}-f_{n-1}
\end{equation}
for all $n \geq 2$.
Recall that the defining recurrence was
\begin{equation}
f_{n+1} = (f_{n}^2+1)/f_{n-1}.
\end{equation}
Rather than prove that the sequence of polynomials
defined by equation (2) 
(with the initial conditions $f_0 = f_1 = x$)
satisfies (1),
we will prove that the sequence of polynomials
defined by equation (1) 
(with the initial conditions $f_0 = f_1 = x$)
satisfies (2).
For the rest of this proof,
$f_0,f_1,\dots$ denotes the sequence given by recurrence (1).
 
To show that (2) holds, we must prove that
$f_{n+1} f_{n-1} = f_{n}^2 + 1$.
Replacing $f_{n+1}$ by $(2+1/x^2)f_{n}-f_{n-1}$ in this equation,
we can rewrite the desired equality in the form
\begin{equation}
f_n^2+f_{n-1}^2+1 = (2+1/x^2) f_n f_{n-1}.
\end{equation}
We will prove this by induction.
If $n=1$, it is simple to check the truth of (3) directly.
Otherwise, we may assume as an induction hypothesis that
\begin{equation}
f_{n-1}^2+f_{n-2}^2+1 = (2+1/x^2) f_{n-1} f_{n-2}.
\end{equation}
To derive (3) from (4), substitute $f_{n}=(2+1/x^2)f_{n-1}-f_{n-2}$ into (3)
to obtain
\begin{eqnarray*}
& ((2+1/x^2)f_{n-1}-f_{n-2})^2 + f_{n-1}^2 + 1 = & \\
& (2+1/x^2) ((2+1/x^2)f_{n-1}-f_{n-2}) f_{n-1}; &
\end{eqnarray*}
expanding and cancelling, we get
$$-2(2+1/x^2)f_{n-1}f_{n-2} + f_{n-2}^2 + f_{n-1}^2 + 1 = 
-(2+1/x^2) f_{n-1} f_{n-2}$$
or
$$f_{n-2}^2 + f_{n-1}^2 + 1 = (2+1/x^2) f_{n-1} f_{n-2},$$
which is (4).
That is, (3) is algebraically equivalent to (4),
subject to the substitution $f_{n}=(2+1/x^2)f_{n-1}-f_{n-2}$.
Hence (4) implies (3),
and the claim follows by induction.

(It may also be possible to prove that the sequence defined by (2)
satisfies (1), but I don't see a way to do it.)

\item[(b)] {\it Express $\sum_{n=0}^\infty f_n(x) y^n$ 
as a rational function of $x$ and $y$.}

Call this generating function $F(x,y)$.
Multiplying $F(x,y) = x + xy + \dots$ by 
$1-(2+1/x^2)y+y^2$
and using the recurrence relation proved above,
we have
$(1-(2+1/x^2)y+y^2)F(x,y) = x-(x+1/x)y$,
so that
$$F(x,y) = \frac{x-(x+1/x)y}{1-(2+1/x^2)y+y^2}.$$
We can check this:
If we tell Maple
\begin{verbatim}
expand(taylor((x-(x+1/x)*y)/(1-(2+1/x^2)*y+y^2),y,5));
\end{verbatim}
we get the expected answer.

(Technical aside: The above calculation is rigorously understood
to be taking place in the ring of formal power series in the variable $y$
in which the coefficient ring is the ring of
all rational functions in the variable $x$.
It can be shown that in this ring,
any element whose constant term is 1
(a priori the constant term could be any rational function of $x$) 
has a multiplicative inverse,
so the quotient makes sense.
Indeed, it would also be acceptable to write the generating function
as $$\frac{x^2-(x^2+1)y}{x^2-(2x^2+1)y+x^2y^2}$$
because the denominator of this expression, too,
has a multiplicative inverse in the ring of
formal power series being considered.)

\end{itemize}
\end{enumerate}

\noindent
Incidentally, with recurrence (1) in hand
it is easy to prove that 
$$f_n = \sum_{k=1}^{n} {n-2+k \choose 2k-2} x^{3-2k}.$$
Indeed, assuming (for purposes of induction)
that this formula holds for $f_{n-1}$ and $f_{n-2}$,
we have
\begin{eqnarray*}
f_n & = & (2+1/x^2)f_{n-1}-f_{n-2} \\
& = & 2 \sum_{k=1}^{n-1} {n-3+k \choose 2k-2} x^{3-2k}
      + \sum_{k=1}^{n-1} {n-3+k \choose 2k-2} x^{1-2k} \\
&   & - \sum_{k=1}^{n-2} {n-4+k \choose 2k-2} x^{3-2k} \\
& = &   \sum_{k=1}^{n-1} 2 {n-3+k \choose 2k-2} x^{3-2k}
      + \sum_{k=2}^{n}     {n-4+k \choose 2k-4} x^{3-2k} \\
&   & - \sum_{k=1}^{n-2}   {n-4+k \choose 2k-2} x^{3-2k} \\
& = & \sum_{k=1}^n {n-2+k \choose 2k-2} x^{3-2k} .
\end{eqnarray*}
The last equality requires some checking,
coefficient by coefficient,
and the analysis splits into several cases.
For $k = 1$, we have
$$2 {n-2 \choose 0} - {n-3 \choose 0} = {n-1 \choose 0}$$
which is just $2-1=1$;
for $k = n-1$, we have
$$2 {2n-4 \choose 2n-4} + {2n-5 \choose 2n-6} = {2n-3 \choose 2n-4}$$
which is just $2+(2n-5)=(2n-3)$;
for $k = n$, we have
$${2n-4 \choose 2n-4} = {2n-2 \choose 2n-2}$$
which is just $1 = 1$;
and for $1 < k < n-1$, we have
$$2{n-3+k \choose 2k-2} + {n-4+k \choose 2k-4} - {n-4+k \choose 2k-2} =
{n-2+k \choose 2k-2},$$
which can be proved by successively substituting
$${n-2+k \choose 2k-2} = {n-3+k \choose 2k-2} + {n-3+k \choose 2k-3},$$
$${n-3+k \choose 2k-2} = {n-4+k \choose 2k-2} + {n-4+k \choose 2k-3},$$
and
$${n-3+k \choose 2k-3} = {n-4+k \choose 2k-3} + {n-4+k \choose 2k-4}.$$
\end{document}


