\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#3: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
{\it Consider the sequence
$1,1,1,3,3,7,9,17,25,...$
satisfying the initial conditions
$a_0 = a_1 = a_2 = 1$
and the recurrence relation
$a_n = 2a_{n-2} + a_{n-3}$.
Write the generating functions $A(x) = \sum_{n=0}^{\infty} a_n x^n$
as a rational function of $x$,
expressed in simplest terms.}
If we write the recurrence in the form,
$1 a_n - 0 a_{n-1} - 2 a_{n-2} - 1 a_{n-3} = 0$
we see that the denominator of the generating function will be
$1 - 0 x - 2 x^2 - 1 x^3$.
Multiplying $1+x+x^2+3x^3+3x^4+7x^5+9x^6+17x^7+25x^8+\dots$
by $1-2x^2-x^3$, we get $A(x) = (1+x-x^2)/(1-2x^2-x^3)$.
If we have access to Maple, we can easily check this answer
by giving it the query
\begin{verbatim}
taylor((1+x-x^2)/(1-2*x^2-x^3),x,10);
\end{verbatim}
\item[(b)]
{\it Find an exact formula for $a_n$.}
The command
\begin{verbatim}
convert((1+x-x^2)/(1-2*x^2-x^3),parfrac,x);
\end{verbatim}
(``convert $(1+x-x^2)/(1-2x^2-x^3)$ into partial fractions,
to the extent that one can do this without introducing
irrational numbers'')
takes us part of the way there, by telling us that $A(x)$ is
$-1/(1+x)$ plus $(2-2x)/(1-x-x^2)$.
(Actually, Maple writes the answer as
\begin{verbatim}
-1/(x+1)+2*(x-1)/(x^2+x-1)
\end{verbatim}
and leaves it to us to notice that in this context,
it makes more sense to list the coefficients of polynomials
from lowest degree to highest rather than the other way around.)
The coefficient of $x^n$ in $-1/(1+x)$ is $(-1)^{n+1}$,
and we can compute the coefficient of $x^n$ in
$2(x-1)/(x^2+x-1)$ by the procedure that Wilf uses
in his treatment of the Fibonacci numbers;
or, we can be clever and hitch a ride
on the already-known formula for Fibonacci numbers.
If we subtract $-1/(1+x)=-1+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+\dots$
from $A(x)=1+x+x^2+3x^3+3x^4+7x^5+9x^6+17x^7+25x^8+\dots$,
we get $2+0x+2x^2+2x^3+4x^4+6x^5+10x^6+16x^7+26x^8+\dots$;
if we subtract 2 from this g.f.\ and divide by $2x^2$,
we get $f(x)=1+x+2x^2+3x^3+5x^4+8x^6+13x^7+\dots$,
which Wilf has already analyzed for us:
the coefficient of $x^n$ in this g.f.\ is
$(\alpha^{n+1}-\beta^{n+1})/\sqrt{5}$,
where $\alpha = \frac{1+\sqrt{5}}{2}$
and $\beta = \frac{1-\sqrt{5}}{2}$.
So the coefficient of $x^n$ in
$2+0x+2x^2+2x^3+4x^4+6x^5+\dots$
is $2(\alpha^{n-1}-\beta^{n-1})/\sqrt{5}$,
and the coefficient of $x^n$ in $A(x)$
is $2(\alpha^{n-1}-\beta^{n-1})/\sqrt{5}\:-\:(-1)^n$.
\item[(c)]
{\it Why did I use the recurrence
$a_n = 2a_{n-2} + a_{n-3}$
for this problem instead of the more natural ``Tribonacci'' recurrence
$a_n = a_{n-1} + a_{n-2} + a_{n-3}$?}
Because the denominator $1-x-x^2-x^3$
doesn't factor nicely;
it has three messy irrational roots.
\end{itemize}
\end{enumerate}
\end{document}
\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}
\end{enumerate}
\end{document}