Solving a difference equation using linear algebra. Let $\mathbb{N}_0=\{0,1,2,...\}$be the set of non-negative integers.  Let $Y:\mathbb{N}_0\to\mathbb{R}^n$. Suppose that $Y$ satisfies a first order constant coefficient difference equation $Y(k+1)=AY(k)$ for some matrix $A$ in $M_{n\times{n}}(\mathbb{R})$and all k in $\mathbb{N_0}$ and $Y(0)=m$ for some $n\times{1}$ constant vector $m$.
$1$. Assume that $P^{-1}AP=diag(\lambda_1,...,\lambda_n)$is diagonal and let $Z(k)=P^{-1}Y(k)$. Prove that the $i$-th coordinate of $Z(k)$ has the form $z_{i}(k)=z_{i}(0)\lambda_{i}^{k}$.
$2$.Let $x:\mathbb{N}_0\to\mathbb{R}$. For fixed $n$ and all $k$ in $\mathbb{N}_0$, suppose that $x(k+n)+a_{n-1}x(k+n-1)+...+a_1x(k+1)+a_0x(k)=0$
and set $Y(k)=[x(k),x(k+1),...,x(K+n-1)]^T$. In terms of the constants $a_0,a_1,...,a_{n-1}$, find a matrix $A$ such that $Y(k+1)=AY(k)$ for all $k$ in $\mathbb{N}_0$.
I was attempted to solve this problem but I couldn't figure it out how to do it. Here is my attempt:
Since the initial condition is given. $Y(0)=m$, we know that $Y(1)=AY(0)=Am$, so we have $Y(k)=A^km$. And since $P^{-1}AP=diag(\lambda_1,..,\lambda_n)$, we know that $A$ can be diagonalized. What's next? I was stuck here and I couldn't solve part $2$ without knowing the matrix $A$. Can someone help me out please? Thank you very much.
 A: ${\bf 1.}\ $If $P^{-1}AP=D$ then $$A^k=PD^kP^{-1}\qquad(k\geq0)\ .$$
It follows that
$$y(k)=A^k y(0)=A^k m=P\>D^k z\qquad(k\geq0)$$
with $z:=P^{-1}m$. As $D={\rm diag}(\lambda_1,\ldots,\lambda_n)$ it is obvious that
$$(D^k z)_i= \lambda_i^k z_i\qquad(1\leq i\leq n)$$
for all $k\geq0$. This means that the $D^k z$ can be computed in a very simple way, so that a single matrix multiplication then suffices to get from the $D^k z$ to the desired $y(k)$.
${\bf 2.}\ $This second exercise aims at the following fact: As in the theory of linear ODEs, an $n^{\rm th}$ order linear recurrence for a scalar function $x:\>{\mathbb N}\to{\mathbb R}$ can be translated into a first order linear recurrence for a vector-valued function $y:\>{\mathbb N}\to{\mathbb R}^n$. To this end define the vector $y(k)$ by
$$y(k):=\bigl(x(k), x(k+1),\ldots, x(k+n-1)\bigr)\qquad(k\geq0)\ .$$
Then
$$y(k+1)=\bigl(x(k+1), x(k+2),\ldots, x(k+n)\bigr)\qquad(k\geq0)\ .$$
Writing this out in components we see that
$$\bigl(y(k+1)\bigr)_i=\bigl(y(k)\bigr)_{i+1}\qquad(1\leq i\leq n-1)\ ,\tag{1}$$
while the last component of $y(k+1)$ has to be inferred from the recurrence relation for the $x(k)$:
$$\eqalign{\bigl(y(k+1)\bigr)_n&=x(k+n)=-\bigl(a_0 x(k)+a_1 x(k+1)+\ldots+a_{n-1}x(k+n-1)\bigr)\cr
&=-a_0 \bigl(y(k)\bigr)_1-a_1 \bigl(y(k)\bigr)_2-\ldots-a_{n-1}\bigl(y(k)\bigr)_n\cr}\tag{2}$$
The equations $(1)$ and $(2)$ can be condensed to a single matrix recurrence
$$y(k+1)=Ay(k)$$
with a certain constant matrix $A$. I leave it to you to set up this matrix.
