Recurrence relation with Z-Transform I'm revising the Z-Transform. I am looking at the book which gives an example of how to solve the recurrence relation
$$x_{k+2} - 3x_{k+1} +2x_k = 1$$
where $x_0 = 0$ and $x_1 = 1$. The book uses the left-shift theorem which states that if $Z[x_k] = F(z)$ then $Z[x_{k+m}] = z^m F(z) - (z^m x_0 + z^{m-1} x_1 + z^{m-2} x_2 + \dots + z x_{m-1})$. Using this, we can find the solution.
However, I remember 10 years ago when I did a lot of signal processing, I used to invert the recurrence relation so that I can use the right-shift theorem which is simpler. So I would convert the above recurrence relation to
$$x_k - 3 x_{k-1} + 2 x_{k-2} = 1$$
and then use the right-shift theorem which states: if $Z[x_k] = F(z)$ then $Z[x_{k-m}] = z^{-m}F(z)$. Using this technique, I get a different result to the book. I must have made a mistake because I also don't get the opportunity to input the initial conditions using the right shift theorem. What have I done wrong? I don't need the recurrence relationship solved - the book solves it. I just don't know if what I remember is true or if I'm mistaken.
 A: In this case the result of the question in using the right-shift form is correct in concept. In this case the initial terms are not required.
The process becomes more clear when solving this recurrence relation:
$$ x_{k} - 3 \, x_{k-1} + 2 \, x_{k-2} = 1 $$
by the following method.
\begin{align}
x_{k} - 3 \, x_{k-1} + 2 \, x_{k-2} &= 1 \\
F - \frac{3}{t} \, F + \frac{2}{t^2} \, F &= \frac{t}{t-1} \\
(2 - 3 t + t^2) \, F &= \frac{t^3}{t-1} \\
F &= \frac{t^3}{(t-1)^2 \, (t-2)} \\
&= \frac{1}{\left(1 = \frac{1}{t}\right)^2 \, \left(1 - \frac{2}{t}\right)} \\
&= - \frac{1}{(\left(1 - \frac{1}{t}\right)^2} - \frac{2}{1- \frac{1}{t}} + \frac{4}{1- \frac{2}{t}} \\
&= \sum_{n=0}^{\infty} ( 2^{n+2} - n - 3 ) \, t^{-n},
\end{align}
where
$$ F(t) = \sum_{n=0}^{\infty} x_{n} \, t^{-n}. $$
The solution of the difference equation is then
$$ x_{k} = 2^{k+2} - k - 3. $$
This result may be a shifted form of result.
When considering the original form
$$ y_{n+2} - 3 \, y_{n+1} + 2 \, y_{n} = 1$$
the general solution is
$$ y_{n} = c_{0} \, 2^n - n - 1 + c_{1} $$
which maintains the same form as the result found for $x_{k}$.
