Proving convergence of Newton's method Consider the recursive sequence
$$ z_{n+1} = {1 \over 2}\left ( z_n + {1 \over z_n} \right )$$
where we start at some point $z_0 = x_0 + i y_0 \in \mathbb C$. This is Newton's formula to find the roots of $p(x) = x^2 -1$. By taking the limit on both sides we see that if the sequence converges then the limit must be either $1$ or $-1$. But:

How do you prove this sequence converges? Of course this is the very
  first thing we must show, even before calculating the limit!

Normally I would show it's a Cauchy sequence but I don't see how to do that here. 

First of all, the sequence doesn't converge if $\newcommand{\real}{\operatorname{Re}}\real z_0 = 0$. You can check that if $z_0$ is purely imaginary, then so is $z_1$, and inductively all $z_n$. 
On the other hand, it's also easy to check that if $\real z_0 > 0$, then $\real z_1 > 0$, so sequences that start in the left half-plane stays there. Similarly, sequences that start in the right half-plane stay in the right  half-plane.
Now, assume that $\real z_0 > 0$. The analysis will be easier if we work on the unit disc instead of the half-plane. The mapping
$$
f(z) = \frac{i+z}{i-z}
$$
maps the unit disc conformally onto the right half-plane. Define a new sequence of points: $w_n = f^{-1}(z_n)$. Then (after some algebra)
$$
w_{n+1} = f^{-1}(z_{n+1}) = f^{-1}(N(f(w_n)) = -iw_n^2
$$
where $N(z) = \frac12(z+\frac1z)$ is the Newton iteration.
Here it is clear that $w_n$ tends to $0$ if we start inside the unit disc, so $z_n$ tends to $f(0) = 1$.
The case where $z_0$ is in the left half-plane can be handled in a similar way. This corresponds to a starting point $w_0$ outside the unit disc, and $w_n \to \infty$. I.e. $z_n \to f(\infty) = -1$.
Note: the convergence here is deceptively simple. For higher degree polynomials, the basins of attraction for the various solutions is very complicated. See Newton fractals for some nice pictures!
