I have been trying to understand various proofs of the convergence of Fixed Point iteration, for instance on Wikipedia:
In each case, however, I simply cannot seem to fathom how and why the factor $|k| < 1$ is exponentiated after the inequalities have been 'combined' or 'applied inductively':
$$|P_n - P| \le K|P_{n-1} - P| \le K^2|P_{n-2} - P| \le \cdots \le K^n|P_0 - P|$$
Any assistance would be received most gratefully.
On
Adopting the notation from Wikipedia, suppose that you have a sequence $(x_n)$ satisfying $\lvert x_n - x_{n-1} \rvert \leq L \lvert x_{n-1} - x_{n-2} \rvert$ for all $n \geq 2$. We want to show that $\lvert x_n - x_{n-1} \rvert \leq L^{n-1} \lvert x_1 - x_0 \rvert$.
We can do this by induction. The claim clearly holds for $n = 1$. Assume that it holds for a given $n$. Then
$$\lvert x_{n+1} - x_n \rvert \leq L \lvert x_n - x_{n-1} \rvert \leq L L^{n-1} \lvert x_1 - x_0 \rvert = L^n \lvert x_1 - x_0 \rvert.$$
Let $f:\mathbb{R}\rightarrow\mathbb{R}$. Suppose there exists some $L>0$ such that $$ \left|f(x)-f(y)\right|\leq L\left|x-y\right|\text{ for each }x,y $$ (in this case, we say $f$ is Lipschitz continuous with Lipschitz constant $L$).
A fixed point iteration is bootstrapped by an initial point $x_{0}$. The $n$-th point is given by applying $f$ to the ($n-1$)-th point in the iteration. That is, $x_{n}=f(x_{n-1})$ for $n>0$. Therefore, for any $m$, \begin{align*} \left|x_{m}-x_{m-1}\right| &=\left|f(x_{m-1})-f(x_{m-2})\right|\\ &\leq L\left|x_{m-1}-x_{m-2}\right|\\ &=L\left|f(x_{m-2})-f(x_{m-3})\right|\\ &\leq L^{2}\left|x_{m-2}-x_{m-3}\right|\\ &\leq\ldots \end{align*} (I think you can deduce the pattern now).