\include{preamble}

\begin{document}

Math 188, Spring 2021

Homework 1

Due: April 9, 2021 11:59PM via Gradescope

~

Solutions must be {\bf clearly} presented. Incoherent or unclear solutions will lose points.

\begin{enumerate}
\item Find a closed formula for the following recurrence relation:
  \begin{align*}
    a_0 &= 1,\ a_1 = 1,\ a_2 = 2,\\
    a_{n} &= 5a_{n-1} - 8a_{n-2} + 4a_{n-3} \qquad (n \ge 3).
  \end{align*}

  
\item Find a closed formula for the following recurrence relation:
  \begin{align*}
    a_0 &= 1,\\
    a_{n} &= 3a_{n-1} + 2^n \qquad (n \ge 1).
  \end{align*}


\item Let $r_1,\dots,r_d$ be distinct numbers. Prove that the sequences $(r_1^n), \dots, (r_d^n)$ are linearly independent by showing that the determinant of $(r_i^{j-1})_{i,j=1,\dots,d}$ is nonzero (interpret $0^0=1$).
  
\item Let $(a_n)_{n \ge 0}$ be a sequence satisfying a linear recurrence relation whose characteristic polynomial is $(t^2-1)^d$.
  \begin{enumerate}
  \item Show that there exist polynomials $p(n)$ and $q(n)$ of degree $\le d-1$ such that
  \[
    a_n = \begin{cases} p(n) & \text{if $n$ is even} \\ q(n) & \text{if $n$ is odd} \end{cases}.
  \]
\item   How does this generalize if the characteristic polynomial is $(t^k-1)^d$?
\end{enumerate}

\item
  \begin{enumerate}
  \item Suppose that $(a_n)_{n \ge 0}$ and $(a'_n)_{n \ge 0}$ both satisfy the same linear recurrence relation of order $d$ and that they agree in $d$ consecutive places, i.e., there exists $k$ such that $a_k=a'_k, a_{k+1}=a_{k+1}', \dots, a_{k+d-1}=a_{k+d-1}'$. Show that these sequences are the same.

  \item Suppose that $(a_n)_{n \ge 0}$ satisfies the linear recurrence relation of order $d$
    \[
      a_n = c_1 a_{n-1} + \cdots + c_d a_{n-d} \qquad \text{for all $n \ge d$}.
    \]
    Show that there is a unique sequence $(b_n)_{n \in \bZ}$ (indexed by {\it all} integers) such that $b_n=a_n$ for $n \ge 0$ and such that
    \[
      b_n = c_1 b_{n-1} + \cdots + c_d b_{n-d} \qquad \text{for all $n \in \bZ$}.
    \]
    Explain how to get a closed form formula for $b_n$.
  \item Consider the Fibonacci sequence $f_0=0$, $f_1=1$, and $f_{n+2}=f_{n+1}+f_n$. How does the negatively indexed Fibonacci sequence relate to the usual one?
  \end{enumerate}
\end{enumerate}

\section{Optional problems (don't turn in)}

\begin{enumerate}
\item Let $p$ be a prime number and let $(a_n)_{n \ge 0}$ be a sequence such that $a_n \in \bZ/p$ and which satisfies a homogeneous linear recurrence relation. Show that the sequence is in fact periodic.

  \item Let $r_1,\dots,r_{d-1}$ be distinct numbers. Prove that the sequences $\alpha_1 = (r_1^n), \dots, \alpha_{d-1} = (r_{d-1}^n), \alpha_d = (nr_{d-1}^{n-1})$ are linearly independent by showing that the determinant of $(\alpha_{i,j-1})_{i,j=1,\dots,d}$ is nonzero (interpret $0^0=1$ and if $r_{d-1}=0$, interpret $\alpha_{d,0}=0$).
\end{enumerate}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
