[proofplan] The proof uses the contraction inequality twice: first to compare the current error $d(x_n,x^*)$ with the next error $d(x_{n+1},x^*)$, and then to compare consecutive step sizes. The fixed point identity $f(x^*)=x^*$ converts the contraction estimate into an inequality involving the iteration sequence. Once the one-step a posteriori bound is obtained, the estimate in terms of the initial displacement follows by iterating the bound on successive increments. [/proofplan] [step:Relate the current error to the next iterate displacement] For each integer $n \ge 0$, the definition of the iterates gives $x_{n+1}=f(x_n)$. Since $x^*$ is a fixed point of $f$, we also have $x^*=f(x^*)$. Applying the triangle inequality in the [metric space](/page/Metric%20Space) $(X,d)$ gives $d(x_n,x^*) \le d(x_n,x_{n+1}) + d(x_{n+1},x^*)$. Using $x_{n+1}=f(x_n)$, $x^*=f(x^*)$, and the contraction hypothesis with the pair $(x_n,x^*)$, we obtain $d(x_{n+1},x^*) = d(f(x_n),f(x^*)) \le c\,d(x_n,x^*)$. Substituting this estimate into the previous inequality yields \begin{align*} d(x_n,x^*) \le d(x_n,x_{n+1}) + c\,d(x_n,x^*) \end{align*} Since $c \in [0,1)$, we have $1-c>0$, so rearranging gives \begin{align*} d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n) \end{align*} [guided] Fix an integer $n \ge 0$. The goal is to estimate the unknown error $d(x_n,x^*)$ using a computable quantity involving iterates. The only available computable displacement near $x_n$ is the step size $d(x_{n+1},x_n)$, so we insert $x_{n+1}$ between $x_n$ and $x^*$ by the triangle inequality: $d(x_n,x^*) \le d(x_n,x_{n+1}) + d(x_{n+1},x^*)$. Now we use the iteration rule and the fixed point property. By definition of the sequence, $x_{n+1}=f(x_n)$. Since $x^*$ is a fixed point, $x^*=f(x^*)$. Therefore the second term can be rewritten as $d(x_{n+1},x^*) = d(f(x_n),f(x^*))$. The contraction hypothesis applies to every pair of points in $X$, so it applies to the pair $(x_n,x^*)$ and gives $d(f(x_n),f(x^*)) \le c\,d(x_n,x^*)$. Combining these two facts gives $d(x_{n+1},x^*) \le c\,d(x_n,x^*)$. Substituting this back into the triangle inequality produces \begin{align*} d(x_n,x^*) \le d(x_n,x_{n+1}) + c\,d(x_n,x^*) \end{align*} We now move the term $c\,d(x_n,x^*)$ to the left: \begin{align*} (1-c)d(x_n,x^*) \le d(x_n,x_{n+1}) \end{align*} Because $c \in [0,1)$, the number $1-c$ is strictly positive, so division by $1-c$ preserves the inequality. Hence \begin{align*} d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n) \end{align*} This is the basic error bound: the current error is controlled by the next step size. [/guided] [/step] [step:Convert the next step size into the current step size] Let $n$ be an integer with $n \ge 1$. Since $x_{n+1}=f(x_n)$ and $x_n=f(x_{n-1})$, applying the contraction hypothesis to the pair $(x_n,x_{n-1})$ gives $d(x_{n+1},x_n) = d(f(x_n),f(x_{n-1})) \le c\,d(x_n,x_{n-1})$. Combining this with the estimate from the previous step gives \begin{align*} d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n) \end{align*} and therefore \begin{align*} d(x_n,x^*) \le \frac{c}{1-c}\,d(x_n,x_{n-1}) \end{align*} This proves the a posteriori estimate for every integer $n \ge 1$. [guided] Fix an integer $n \ge 1$. This lower bound on $n$ is needed because the expression $x_{n-1}$ appears in the estimate. The iteration identities give $x_{n+1}=f(x_n)$ and $x_n=f(x_{n-1})$, so the distance between the next two iterates can be written as $d(x_{n+1},x_n) = d(f(x_n),f(x_{n-1}))$. The contraction hypothesis applies to the pair $(x_n,x_{n-1})$, and therefore $d(f(x_n),f(x_{n-1})) \le c\,d(x_n,x_{n-1})$. Hence $d(x_{n+1},x_n) \le c\,d(x_n,x_{n-1})$. The previous step established, for this same $n$, that \begin{align*} d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n) \end{align*} Substituting the bound on $d(x_{n+1},x_n)$ gives \begin{align*} d(x_n,x^*) \le \frac{c}{1-c}\,d(x_n,x_{n-1}) \end{align*} This proves the a posteriori estimate for every integer $n \ge 1$. [/guided] [/step] [step:Bound every step size by the initial step size] Define the nonnegative sequence $(a_k)_{k=0}^{\infty}$ by \begin{align*} a_k = d(x_{k+1},x_k). \end{align*} For every integer $k \ge 1$, the identities $x_{k+1}=f(x_k)$ and $x_k=f(x_{k-1})$ imply \begin{align*} a_k = d(f(x_k),f(x_{k-1})) \le c\,d(x_k,x_{k-1}) = c\,a_{k-1}. \end{align*} The base case $k=0$ is $a_0 \le c^0 a_0$. The recurrence then gives by induction on $k$ that \begin{align*} a_k \le c^k a_0 \end{align*} for every integer $k \ge 0$. Since $a_0=d(x_1,x_0)$, this says \begin{align*} d(x_{k+1},x_k) \le c^k d(x_1,x_0) \end{align*} for every integer $k \ge 0$. [guided] Define the sequence $(a_k)_{k=0}^{\infty}$ by \begin{align*} a_k = d(x_{k+1},x_k). \end{align*} Each $a_k$ is nonnegative because $d$ is a metric. The recurrence starts only at $k=1$, since it uses $x_{k-1}$. For every integer $k \ge 1$, the identities $x_{k+1}=f(x_k)$ and $x_k=f(x_{k-1})$ give \begin{align*} a_k = d(x_{k+1},x_k) = d(f(x_k),f(x_{k-1})). \end{align*} Applying the contraction hypothesis to the pair $(x_k,x_{k-1})$ yields \begin{align*} a_k \le c\,d(x_k,x_{k-1}) = c\,a_{k-1}. \end{align*} Now we prove the geometric bound by induction. For $k=0$, the assertion is \begin{align*} a_0 \le c^0 a_0, \end{align*} which holds because $c^0=1$. Suppose $k \ge 1$ and $a_{k-1} \le c^{k-1}a_0$. Using the recurrence gives \begin{align*} a_k \le c\,a_{k-1} \le c\,c^{k-1}a_0 = c^k a_0. \end{align*} Thus \begin{align*} a_k \le c^k a_0 \end{align*} for every integer $k \ge 0$. Since $a_0=d(x_1,x_0)$, this is exactly \begin{align*} d(x_{k+1},x_k) \le c^k d(x_1,x_0) \end{align*} for every integer $k \ge 0$. [/guided] [/step] [step:Combine the one-step error estimate with the geometric decay of increments] Let $n$ be an integer with $n \ge 0$. Applying the first estimate from the first step and then using the bound on increments with $k=n$, we get $d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n)$. The increment estimate gives \begin{align*} d(x_{n+1},x_n) \le c^n d(x_1,x_0) \end{align*} Therefore \begin{align*} d(x_n,x^*) \le \frac{c^n}{1-c}\,d(x_1,x_0) \end{align*} This proves the second asserted estimate and completes the proof. [guided] Fix an integer $n \ge 0$. The first step gives the intermediate estimate $d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n)$. The previous step controls this computable increment in terms of the initial displacement. Applying that estimate with $k=n$ gives $d(x_{n+1},x_n) \le c^n d(x_1,x_0)$. Substituting this inequality into the intermediate error estimate yields $d(x_n,x^*) \le \frac{1}{1-c}\,d(x_{n+1},x_n) \le \frac{c^n}{1-c}\,d(x_1,x_0)$. This proves the second asserted estimate for every integer $n \ge 0$. Together with the a posteriori estimate for every integer $n \ge 1$, this completes the proof. [/guided] [/step]