How to prove the norm inequality

Question

Show that if $||T||<1$ and $x^k$ is a sequence defined by $x^{k}=Tx^{k-1}+c$ where $c$ is a given vector,

we have $||x-x^{k}||\le \dfrac{||T||^k}{1-||T||}(||x^{1}-x^{0}||,x\in \Bbb R^n$

Now $||x^{2}-x^{1}||=||T(x^{1})-T(x^0)||\le||T||||x^{1}-x^{0}||$

$||x^{3}-x^{2}||=||T(x^{2})-T(x^1)||\le||T||^2||x^{1}-x^{0}||$ and so on..

In general

$||x^{k}-x^{k-1}||=||T(x^{k-1})-T(x^{k-2})||\le||T||^{k-1}||x^{1}-x^{0}||$

Adding all we get

$||x^{k}-x^{1}||=||T(x^{k-1})-T(x^{k-2})||\le\{||T||+||T||^2+\cdots +||T||^{k-1}\}||x^{1}-x^{0}||$

I understand the series on the RHS converges but I dont understand how to arrive at the given inequality

Can I get some help?

Answer 1

This is just the sum of a geometric progression: $$\|x^k-x^1\|\le\frac{\|T\|-\|T\|^k}{1-\|T\|}\|x^1-x^0\|.$$ Letting $k\to\infty$, $$\|x-x^1\|\le\frac{\|T\|}{1-\|T\|}\|x^1-x^0\|$$ which is the $k=1$ case of what you seek.

In general, for $r>k$ $$\|x^r-x^k\|\le\frac{\|T\|^k-\|T\|^r}{1-\|T\|}\|x_1-x_0\|,$$ and therefore $$\|x-x^k\|\le\frac{\|T\|^k}{1-\|T\|}\|x_1-x_0\|$$ in the limit as $r\to\infty$.