# Existence of $n^{th}$ root

Disclaimer : This is homework (Tagged)

I am trying to prove that Real numbers have nth roots. Most references do the following : Let $a \in \mathbb{R}, n \in \mathbb{N}, n > 0$ Then we consider a set X = {$t | t^n< a$}. Then we prove that X is nonempty (since it contains 0) and that it is bounded above ($a+1$ is an upper bound). Then through the property of Real numbers, this set will have a supremum. Let that supremum be f. Most books now deal with 2 cases : $f^n<a , f^n>a$ and show a contradiction thus proving $f^n = a$ and I am comfortable with this way of doing it. I have finished my homework. Books closed. EOF.

However, is there any way to prove this without the use of contradiction?

-
Actually you reason by contradiction (assuming $f^n\neq a$) and consider only $2$ cases for the contradiction. Do you mean a proof that avoids reasoning by contradiction altogether? Also note you do seem to assume $a>0$ without saying so. –  Marc van Leeuwen Jun 25 '12 at 8:50
@MarcvanLeeuwen, Yes. I mean avoid contradiction altogether. Where did I assume a>0? –  Real_Analysis Jun 25 '12 at 8:52
@Real_Analysis Implicitly when you use "$X$ is non-empty because it contains $0$". –  Ragib Zaman Jun 25 '12 at 8:54
You should be able to show directly that the sequence $x_n=\frac{x_{n-1}}{a}+\frac{a-1}{x_{n-1}}$ converges for suitable values of $x_0$. I think the sequence should be strictly increasing and bounded or sth. So the limit exists and this limit must be the square root of $a$. –  Simon Markett Jun 25 '12 at 9:08
@Real_Analysis: You should be aware that negative numbers don't have square roots (in the reals), aren't you? Then you must have used implicitly that this case is avoided, and Ragib Zaman showed where this happens. –  Marc van Leeuwen Jun 25 '12 at 9:12

The idea: Show the Newton-Raphson interation scheme to find the positive root of $f(x)= x^n-a$ converges, where we fix $n\geq 2, a>0.$ This is sufficient to prove existence, and uniqueness follows from $0<x<y \implies 0< x^n < y^n.$

Newton-Raphson: $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = \frac{1}{n} \left( (n-1)x_k+ \frac{a}{x_k^{n-1}} \right) .$$

Pick $x_0=a.$ If $x_k\to x$ then taking limits of the recurrence and rearranging gives $x^n=a$ as we hope.

We show $(x_k)$ is positive and monotonically decreasing for $k\geq 1$, and thus convergent: By the Arithmetic-Geometric mean inequality,

$$x^n_{k+1} = \frac{1}{n^n} \left( (n-1)x_k+ \frac{a}{x_k^{n-1}} \right)^n = \left( \frac{ x_k + x_k + \cdots x_k + \frac{a}{x_k^{n-1}} }{n} \right)^n \geq x_k^{n-1} \frac{a}{x_k^{n-1}} = a$$ for all $k\geq 0.$ Hence $a/x_k^n\leq 1$ for all $k\geq 1$ so using the recurrence gives: $$nx_{k+1}=(n-1)x_k + \frac{a}{x_k^{n-1}} = x_k\left( n-1 + \frac{a}{x_k^n} \right) \leq x_k(n-1+1) = nx_k$$

so the sequence is decreasing as required.

Simple introduction to Newton-Raphson: The aim is to approximate the root of a function. To do so, take a decently close estimate of the root $x_0.$ Draw the graph of $y=f(x)$ with some root, and mark the point $(x_0, f(x_0))$ which is somewhat near-by. Draw the tangent to the curve at that point, notice that the $x$-intercept of this tangent is a better approximation to the root than $x_0$ was, call it $x_1.$ Repeat this, and in the limit (in "ideal" situations) $x_n$ tends to the root. Simple analytic geometry yields $x_{k+1}$ in terms of $x_k, f(x_k), f'(x_k)$ and we get the Newton-Raphson recurrence.

This is often a very quickly converging method to approximate roots of functions (each iteration doubles the number of accurate decimal places), but it can fail if your initial approximation is too far away, or too close to another root, or if $f'(x_k)=0$ (so that the tangent is horizontal so never intercepts the $x$-axis). For this problem I showed that by choosing $x_0=a$ this method ends up converging (which is something you should strongly suspect to happen by sketching the graph and a few of the tangents), to something that must be a root of $x^n-a.$

-
I'm sure this is a very nice method but I'm just starting out in Real Analysis and Calculus and I have no clue what Newton-Rhapson is. –  Real_Analysis Jun 25 '12 at 8:59
@Real_Analysis: If you want a proof not using contradiction, then you are going to have to construct an $n$th root. Doing so requires somewhat technical tools, one doesn't expect the solution to appear out of the blue as a "deux ex machina". –  Marc van Leeuwen Jun 25 '12 at 9:15
@Real_Analysis Newton-Rhapson is the motivation for where I bring up the sequence from, but you could take the sequence as if it were "pulled from thin air" and it is still a valid proof. Nevertheless, I have added some basic information on the method, it is quite a simple idea and worth knowing about. –  Ragib Zaman Jun 25 '12 at 9:32