\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#4: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
{\it Does there exist a polynomial $p(t)$ of degree 3
such that the linear operator $p(T)$
annihilates the sequence whose $n$th term (for $n \geq 0$)
is $3^n+2^n+1^n$?
Exhibit such a polynomial or explain why none exists.}
Since $T-3I$ annihilates $3^n$,
and $T-2I$ annihilates $2^n$,
and $T-I$ annihilates $1^n$,
the linear operator
$(T-3I)(T-2I)(T-I) = T^3-6T^2+11T-6$ annihilates
$3^n+2^n+1^n$.
\item[(b)]
{\it Same as (a), but with ``degree 3'' replaced by ``degree 4''.}
Any linear operator of the form $(T-cI)(T^3-6T^2+11T-6)$ will do;
e.g., with $c=0$, we get $T^4 - 6T^3 + 11T^2 - 6T$.
\item[(c)]
{\it Same as (a), but with ``degree 3'' replaced by ``degree 2''.}
No. Suppose we have constants $A,B,C$ such that $AT^2+BT+CI$
annihilates the sequence whose $n$th term is $f(n)=3^n+2^n+1^n$.
That is, suppose $Af(n+2)+Bf(n+1)+Cf(n)=0$ for all $n \geq 0$.
Substituting $n=0$, $n=1$, and $n=2$ into this equation we get
$14A+6B+3C=0$, $36A+14B+6C=0$, and $98A+36B+14C=0$.
Since the determinant
$$\left|\begin{array}{rrr}
14 & 6 & 3 \\ 36 & 14 & 6 \\ 98 & 36 & 14 \end{array} \right|$$
is not equal to zero,
the only solution to this linear system is $A=B=C=0$.
\end{itemize}
\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}