Sequences and Contraction of a fixed point Suppose that $g:\mathbb R \to $$\mathbb R$ is a contraction. Then $g$ has a unique
fixed point $c$ and that for any number $x_0$, the sequence $x_0, x_1, x_2,\ldots$ given by
$x_n = g(x_{n-1})$. converges to the fixed point. In certain situations, the speed of convergence may be faster than a rough estimate based only on the contraction constant would suggest.
To be concrete, suppose the fixed point is zero and the contaction constant
is $1/2$. That is, suppose that that $g:\mathbb R \to $$\mathbb R$ satisfies $g(0) = 0$ and that for all $a,b ∈  $$\mathbb R$, $|g(x)-g(y)|<1/2|x-y|$. Let $x_0$ $= 1$. The sequence $x_0, x_1, x_2,\ldots$ converges to $0.$  

(i) For what $n$ can you be certain that $|x_n|<10^{-100}$?

Here is my attempt:
If we let $x = x_n$ and $y = 0$, then we see that, for every $n$
$$
\left|x_{n+1}\right| = \left|g(x_n) - g(0)\right| < \frac{1}{2}\left|x_n - 0\right| = \frac{1}{2}\left|x_n\right|
$$
Can we also say that $|x_2| < 1/2|x_1| < 1/2^{2}$

(ii) If we assume that $g'(0) = 0$ and $|g''(x)|<1$ the sequence ${x_n}\to\ 0$ faster. With these assumptions, for what n can you be certain that $|x_n|<10^{-100}$?
(iii) If we assume that $g'(0) = 0$ and $|g(0)| = 0$, and $g'''(x)<1$, the sequence ${x_n} \to\ 0$ faster still. With these assumptions, for what $n$ can you be certain that $|x_n| < 100^{-100}$?

I am trying to solve this problem, but I can not seem to get through it. I was reading the "Analysis of Numerical Methods" by Isaacson, but he just assumes that things should be known for a beginner. This has been very frustrating because I want to learn this particular problem, but what I was reading does not help. I really tried on this problem but have come to the point of exhaustion. I know if I see the solution I will understand it. Can someone please show me?
 A: Your guess for first question is right, but you have to iterate this "to the end":
$$ \vert x_n \vert < \frac{1}{2} \vert x_{n-1} \vert < \dots < \left ( \frac{1}{2} \right )^n \cdot \vert x_0 \vert$$
So after that you can choose appropriate number $n$.
Intuition behind second and third question is the following. If you have a contraction $f$ with nondegenerate linear part, locally it "looks like" its 
linear part $f_1 = f'(0) x $. "Looks like" means that $f(x) \sim  f_1(x)$ in sense of calculus. When you have some degeneracy in linear terms or quadratic (I think that was meant in third question), locally $f(x)$ is now like $f_2 (x) = f''(0) x^2$ or $f_3(x) = f'''(0) x^3$. So, these two are contractions in some neighbourhood of zero and their speed is faster than speed of linear contraction. Beware that this estimate of contraction speed works only in some neighbourhood of zero. But it's not hard to say that after some finite amount of iteration the image of initial point will fall in this neighbourhood and then you can use more precise estimation. 
A: Nice question by the way. It had me thinking. Your guess about the first part is correct somewhat. The second and third question I assume would be the same.
For part (i) you could have $|x_2|$ $<$ $1/2$ $|x_1|$ $<$ $1/2^{2}$.
