\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[total={6in,8in}]{geometry}

\usepackage{tikz}
%\usepackage{pgfplots}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]

%\usepackage{graphicx}

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{leftmargin=*,label=(\alph*)}

%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\ve}{\varepsilon}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Span}{\mathrm{Span}}
\DeclareMathOperator{\rk}{\mathrm{rank}}
\DeclareMathOperator{\trace}{\mathrm{tr}}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\Sym}{\mathrm{Sym}}
\DeclareMathOperator{\Hom}{\mathrm{Hom}}
\DeclareMathOperator{\diag}{\mathrm{diag}}
\DeclareMathOperator{\rank}{rank}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
  \refstepcounter{problem}\par\medskip
  \def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in

%\pagestyle{empty}

\begin{document}
\centerline{Math 201 Homework for Friday, Week 11}
\bigskip
Due: Friday, November 19.

    


\begin{prob}
   Consider a sequence of numbers~$p_n$ defined recursively  by fixing
      constants~$a$ and~$b$, next assigning
      initial values for~$p_0$ and~$p_1$, and then for~$n\geq1$ letting 
      \[
        p_{n+1}=a p_n+b p_{n-1}.
      \]
      For instance, letting~$a=2$, $b=-1$, $p_0=0$, and~$p_1=1$, we get
      \begin{align*}
        p_0&=0\\
        p_1&=1\\
        p_{n+1}&=2p_n-p_{n-1}\quad\text{for~$n\geq1$},
      \end{align*}
      which defines the sequence
      \[
        0,1,2,3,4,5,6,\dots
      \]
      Given any sequence of this form, we can encode the recursive relation in the following matrix equation:
      \begin{equation}\label{recursive}
    \left(\begin{array}{c}
        p_{n+1}\\
        p_n
    \end{array} \right)
    =
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)
    \left(\begin{array}{c}
        p_n\\
        p_{n-1}
    \end{array} \right).
  \end{equation}
  So we have
  \[
    \left(\begin{array}{c}
        p_2\\
        p_1
    \end{array} \right)
    =
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)
    \left(\begin{array}{c}
        p_1\\
        p_0
    \end{array} \right),
  \]
  which implies
  \[
    \left(\begin{array}{c}
        p_3\\
        p_2
    \end{array} \right)
    =
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)
    \left(\begin{array}{c}
        p_2\\
        p_1
    \end{array} \right)
    =
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)
    \left[
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)
    \left(\begin{array}{c}
        p_1\\
        p_0
    \end{array} \right)
    \right]
    =
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)^2
    \left(\begin{array}{c}
        p_1\\
        p_0
    \end{array} \right),
  \]
  and so on.  In general, we have
  \begin{equation}\label{power}
    \left(\begin{array}{c}
        p_{n+1}\\
        p_n
    \end{array} \right)
    =
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right)^n
    \left(\begin{array}{c}
        p_1\\
        p_0
    \end{array} \right).
  \end{equation}
  Let
  \[
  A = 
    \left(\begin{array}{cc}
        a&b\\
        1&0
    \end{array} \right).
  \]
  and suppose~$A$ is diagonalizable.  Take~$P$ so that
  \[
    P^{-1}AP=D=\diag(\lambda_1,\lambda_2).
  \]
  We have seen that it follows that~$A^n=PD^nP^{-1}$, so that
  equation~\eqref{power} becomes
  \[
    \left(\begin{array}{c}
        p_{n+1}\\
        p_n
    \end{array} \right)
    =
    PD^nP^{-1}
    \left(\begin{array}{c}
        p_1\\
        p_0
    \end{array} \right)
    =
    P
    \left(\begin{array}{cc}
        \lambda_1^{n}&0\\
        0&\lambda_2^{n}
    \end{array} \right)
    P^{-1}
    \left(\begin{array}{c}
        p_1\\
        p_0
    \end{array} \right).
  \]
  Thus, we get a closed form expression for~$p_n$ in terms of powers of the eigenvalues
  of~$A$ (just take the second component of the product on the right-hand side
  of the above equation).
  
  Let~$a=b=1$,~$p_0=0$, and~$p_1=1$. 
  \begin{enumerate}
    \item Write out the first several values for the sequence~$(p_n)$.
    \item Write the corresponding matrix equation, as \eqref{recursive} above.
    \item Diagonalize the matrix~$A$ and compute the corresponding equation
      for~$p_n$ in terms of powers of the eigenvalues of~$A$.
  
      You may find the following
      notation useful:
      \[
        \phi = \frac{1+\sqrt{5}}{2}\quad\text{and}\quad
        \overline{\phi} = \frac{1-\sqrt{5}}{2},
      \]
      with useful relations~$\phi\overline{\phi}=-1$, $\phi^2=\phi+1$,
      and~$\phi+\overline{\phi}=1$. ({\bf Warning:}  You will want to make sure
      you get the diagonalization perfect.  This will take some time.  Using the
    above notation as much as possible will help.)
       \item As in the first example above, let $a=2$, $b=-1$, $p_0=0$ and $p_1=1$. What happens when you try to use the method above to find a closed formula for $p_n$?
       \end{enumerate}
\end{prob}
\begin{prob}
  One of the reasons we like diagonalization is  because computing the powers of the matrix is easy  if it is diagonalized (see previous exercise). In this exercise we explore the powers of Jordan blocks. Recall that a $2\times 2$ Jordan block is a matrix of the form 
  \[ J=\begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix},\]
  for some $\lambda \in F$. 
  \begin{enumerate}
   \item For $J$ as above, compute $J^2$, $J^3$ and $J^4$. For a natural number $n$, make a conjecture for the value of $J^n$.
   \item Prove your conjecture. (\emph{Hint:} You probably want to use induction.)
   \item (BONUS:) Repeat (a) and (b) above for a $3\times 3$ Jordan block:
   \[ \begin{pmatrix} \lambda & 1 & 0\\ 0 & \lambda & 1 \\ 0 & 0 & \lambda\end{pmatrix}.\]
  \end{enumerate}
\end{prob}
\end{document}
