Recurrence equation to solve

Question

Given $$x_k=(I-aP)x_{k-1}-aq$$ I need to prove that it is equal to $$x_k=(I-aP)x_0-kaq$$

Answer 1

$$x_1=(I-aP)x_{0}-aqI\\ x_2=(I-aP)x_{1}-aqI\\ x_3=(I-aP)x_{2}-aqI\\ ...\\ x_{k-1}=(I-aP)x_{k-2}-aqI\\ x_k=(I-aP)x_{k-1}-aqI$$

From that you can multiply equation $i$ by $(I-aP)^{k-i}$ and write:

$$(I-aP)^{k-1}x_1=(I-aP)^{k}x_{0}-(I-aP)^{k-1}aq\\ (I-aP)^{k-2}x_2=(I-aP)^{k-1}x_{1}-(I-aP)^{k-2}aq\\ (I-aP)^{k-3}x_3=(I-aP)^{k-2}x_{2}-(I-aP)^{k-3}aq\\ ...\\ (I-aP)x_{k-1}=(I-aP)^2x_{k-2}-(I-aP)aq\\ x_k=(I-aP)x_{k-1}-aqI$$

Now you can sum every equation and get:

$$x_k=(I-aP)^{k}x_0-aq[I+(I-aP)+(I-aP)^2+...(I-aP)^{k-1}]$$

We also have:

$$[I+(I-aP)+(I-aP)^2+...(I-aP)^{k-1}][I-(I-aP)]=I-(I-aP)^k$$

If $P^{-1}$ exist and $a\ne 0$ then

$$I+(I-aP)+(I-aP)^2+...(I-aP)^{k-1}=\frac{1}{a}P^{-1}[I-(I-aP)^k]$$

Finaly the equation would be

$$x_k=(I-aP)^{k}x_0-qP^{-1}[I-(I-aP)^k]$$

PS.: The relation that you are trying to prove is FALSE.

Answer 2

Hint: Let $x_k=y_k+b$ and then $$ y_k+b=(I-aP)(y_{k-1}+b)-aq $$ Try to get a condition for $b$ such that $y_k=(I-aP)y_{k-1}$.