Find general sequence equation linear algebra Suppose that the sequence $x_0, x_1, x_2,\dots$ is defined by $x_0 = 7$, $x_1 = 2$, and $x_{k+2} = −x_{k+1}+2x_k$ for $k\geq0$. Find a general formula for $x_k$. Be sure to include parentheses where necessary, e.g. to distinguish $1/(2k)$ from $1/2k$.  
I have no idea how to do this question! Someone please help.
 A: Observe that $$x_{k+2}-x_{k+1}=-2(x_{k+1}-x_k)$$ so we have  $$\begin{aligned}x_k-x_{k-1}&=-2(x_{k-1}-x_{k-2})\\x_{k-1}-x_{k-2}&=-2(x_{k-2}-x_{k-3})\\\vdots\\ x_2-x_1&=-2(x_1-x_0)\end{aligned}$$ and hence summing all those we get $$x_k-x_1=-2(x_{k-1}-x_0)$$ or equivalently $$x_k+2x_{k-1}=x_1+2x_0\tag1.$$ Now, if $k$ is even, using $(1)$ we get the following chain of equalities: $$\begin{aligned}x_k-4x_{k-2}&=-(x_1+2x_0)\\4x_{k-2}-4^2x_{k-4}&=-4(x_1+2x_0)\\4^2x_{k-4}-4^3x_{k-6}&=-4^2(x_1+2x_0)\\\vdots\\4^{(k-2)/2}x_2-4^{k/2}x_0&=-4^{(k-2)/2}(x_1+2x_0)\end{aligned}$$ so summing those we get $$x_k-4^{k/2}x_0=-\left(1+4+4^2+\cdots+4^{(k-2)/2}\right)(x_1+2x_0)=-\dfrac{4^{k/2}-1}{3}(x_1+2x_0)$$ so $$x_k=\dfrac{2^k(x_0-x_1)}{3}+\dfrac{2x_0+x_1}{3},\hspace{10pt}\text{if $k$ is even.}\tag2$$ Now, if $k$ is odd just use the original recursion $x_{k+1}=-x_k+2x_{k-1}$ because since $k+1$ and $k-1$ are both even we can use $(2)$ and get $$x_k=-\dfrac{2^k(x_0-x_1)}{3}+\dfrac{2x_0+x_1}{3},\hspace{10pt}\text{if $k$ is odd.}\tag3$$ Thus one can see from $(2)$ and $(3)$ that $$\boxed{x_k=\dfrac{(-2)^k(x_0-x_1)}{3}+\dfrac{2x_0+x_1}{3},\hspace{10pt}\text{for all $k$}}$$ and hence using $x_0=7$ and $x_1=2$ we get $$x_k=\dfrac{(-2)^k\cdot5}{3}+\dfrac{16}{3}.$$
A: Just to show an alternative way, through generating function.
Allow me to change notation from $x$ to $a$ to avoid confusion in the following.
Starting from your recurrence
$$
\left\{ \begin{gathered}
  a_{\,0}  = 7 \hfill \\
  a_{\,1}  = 2 \hfill \\
  a_{\,k + 2}  =  - a_{\,k + 1}  + 2a_{\,k}  \hfill \\ 
\end{gathered}  \right.
$$
rewrite it so as to incorporate the initial conditions:
$$
\left\{ \begin{gathered}
  a_{\,k < 0}  = 0 \hfill \\
  a_{\,k}  =  - a_{\,k - 1}  + 2a_{\,k - 2}  + 9\left[ {k = 1} \right] + 7\left[ {k = 0} \right] \hfill \\ 
\end{gathered}  \right.
$$
where $[P]$ indicates the Iverson bracket
$$
\left[ P \right] = \left\{ {\begin{array}{*{20}c}
   1 & {P = TRUE}  \\
   0 & {P = FALSE}  \\
 \end{array} } \right.
$$
Then multiply by $z^k$ and sum up
$$
\begin{gathered}
  \sum\limits_{0\, \leqslant \,k} {a_{\,k} z^{\,k} }  =  - \sum\limits_{0\, \leqslant \,k} {a_{\,k - 1} z^{\,k} }  + 2\sum\limits_{0\, \leqslant \,k} {a_{\,k - 2} z^{\,k} }  + 9\sum\limits_{0\, \leqslant \,k} {\left[ {k = 1} \right]z^{\,k} }  + 7\sum\limits_{0\, \leqslant \,k} {\left[ {k = 0} \right]z^{\,k} }  =  \hfill \\
   =  - z\sum\limits_{0\, \leqslant \,k} {a_{\,k - 1} z^{\,k - 1} }  + 2z^2 \sum\limits_{0\, \leqslant \,k} {a_{\,k - 2} z^{\,k - 1} }  + 9z + 7 \hfill \\ 
\end{gathered} 
$$
So we get:
$$
\sum\limits_{0\, \leqslant \,k} {a_{\,k} z^{\,k} }  = F(z) =  - zF(z) + 2z^2 F(z) + 9z + 7
$$
$$
\begin{gathered}
  F(z) = \frac{{9z + 7}}
{{1 + z - 2z^2 }} =  - \frac{{9z + 7}}
{{\left( {2z + 1} \right)\left( {z - 1} \right)}} = \frac{5}
{{3\left( {2z + 1} \right)}} + \frac{{16}}
{{3\left( {1 - z} \right)}} =  \hfill \\
   = \frac{5}
{3}\sum\limits_{0\, \leqslant \,k} {\left( { - 2} \right)^{\,k} z^{\,k} }  + \frac{{16}}
{3}\sum\limits_{0\, \leqslant \,k} {z^{\,k} }  \hfill \\ 
\end{gathered} 
$$
$$
a_{\,k}  = \frac{{5\left( { - 2} \right)^{\,k}  + 16}}
{3}
$$
