R = N ^ (N ^ (N ^ ...)).
analysis/tower Added material
Problem
R = N ^ (N ^ (N ^ ...)). What is the maximum N>0 that will yield a finite R?
Show solution
ANSWER: e^(1/e)
We want
R = N ^ (N ^ (N ^ ...)) (1)
Note that this is not the same as R = (((N ^ N) ^ N) ^ N) ...
Then R is the limit of the sequence N, N^N, N^(N^N), ... and is a
function of N on a suitable domain. Obviously N = 1 yields R = 1,
and we want the maximum N for which R exists, so we need only consider
N >= 1 and will assume this from now on. Then if N2 > N1, we must have
N2^N2 > N1^N1, N2^(N2^N2) > N1^(N1^N1), and so on; and thus R2 > R1 if
they exist. That is, where the function R of N exists, it is monotone
increasing. Therefore N as a function of R is also monotone increasing
in the range of values of N for which R exists.
We will now examine N as a function of R. Substituting equation (1)
into itself, we get
R = N^R (2)
Taking the logarithm of both sides of (2):
ln(R) = R * ln(N)
That is:
ln(N) = ln(R) / R
Exponentiating:
N = R^(1/R) (3)
We check for a local maximum by differentiating (3) and setting the
derivative to zero:
dN/dR = (1 - ln(R)) / R^2 = 0 (4)
The solution to this is R = e, and it is a genuine local maximum of (3)
if the second derivative is negative at that point:
d2(N)/d2(R) | R=e = (2 * ln(R) - 3) / R^3 | R=e = -1 / e^3 < 0
Thus equation (3) and therefore (2) ceases to yield the monotone increasing
behavior that equation (1) does, at the point where R = e and therefore
(by (3)) N = e^(1/e). Since (1) was monotone increasing throughout the
domain where R exists, this is the maximum N for which R can exist.
It remains to show that R exists and equals e for this value of N.
This will be the case if (e^(1/e))^x <= e for all e^(1/e) <= x <= e.
But this is obvious since (e^(1/e))^x is monotone increasing for the
applicable values of x, and (e^(1/e))^e = e^1 = e.
Additional material
[ Editor: the following postings answer a broader form of the question,
by Steve Fenner <byrd@sphinx.uchicago.edu>: ]
> For what real numbers A > 0 is A^A^A^... defined? That is, for what
> A > 0 does the sequence {a_0, a_1, a_2, ...} defined by
> a_0 = 1,
> a_(n+1) = A^(a_n) (for any n >= 0)
> converge?
The convergence of this formula was studied by Euler. Perhaps more than
you ever wanted to know about this is covered in "Exponentials
Reiterated" by R. Arthur Knoebel, American Mathematical Monthly, 88
(1981) pp 235-252. Knoebel gives four pages of bibliography on this and
related questions.
An open question in 1981 was: where does z^(z^(z^... converge for
*complex* z? This is a fascinating question. The answer is related to
the Mandelbrot set. Robert Devaney has done research on the iterated
complex exponential z -> c * exp(z) and its Julia set. (A beautiful
picture of the corresponding analog of the Mandelbrot set for this
mapping appears on the cover of his book, "Chaotic Dynamical Systems").
The question of convergence of z -> z^(z^(z^... generalizes into the
question of the dynamical behavior of the iteration
z -> x^z = exp(ln(x) * z). Ignore for the moment the multiple sheets
introduced by ln...
Region 1: for what complex y does z -> exp(y * z) converge?
(start with z=0)
Region 2: for what complex y is z -> exp(y * z) bounded?
Characterize those regions where this iteration has an
attractive periodic orbit. (For example, z -> x^z has
a period 2 orbit as x -> 0). I think there are orbits
of all periods.
Region 3: For what complex y does z -> exp(y * z) diverge?
Oh yes, Knoebel threw out one more challenge which I will leave to those
more perspicacious than I am: Can Ackermann's function be analytically
continued in the complex plane?
-- Kevin McCarty <Kevin_P_McCarty@cup.portal.com>
My claim: I believe that the following is one correct way of defining
an iterated exponentiation:
x = A^A^A^A... iff x = A^x
The -> direction is somewhat clear, but I can see that one could still
argue against it. Suppose that ... means take it omega times, then
taking it omega+1 might be different. This is possible and I'll
generate an example for a different function if there is any interest.
The <- direction is more questionable. But I still argue that it is
one (not THE ONLY) definition that makes sense. Here is my
`reasoning': if x = A^x then x=A^A^...A^x for any number of A's even in
the limiting case (with the wave of my hands you can forget the x).
My definition (above) is similar to the one that I think is
conventionally used or at least the one Silverman had in mind. This
definition is: x = A^A^A... iff the sequence (1, A^1, A^A^1, A^A^A^1,
...) converges to x.
Comparing these two definitions we see (not completely trivialy) that
if x = A^A^A... by the second then it is by the first. But the converse
is not true. Also we see that the second will always give a unique
solution. The first does not guarantee a unique solution, there are
cases where there are multiple solutions. But I say that each of these
solutions is just as valid as any other and the the choice of a unique
one is arbitrary.
Analytically, the first one says x = A^A^A... iff x is any fixed point
of the function A^x. The second definition says that x=A^A^A... iff x
is a fixed point of A^x which is reachable from 1. I see no god-given
reason to restrict ourselves to fixedpoints reachable from 1.
Under my definition we can find the answers graphically. x=A^x is
simply the intersection of the curves y=x and y=A^x. So just draw these
curves and the x corrdinate of their intersection is the answer.
There are not three cases as I stated earlier, but four maybe five. I
haven't found the fifth yet, but I suspect it exists based upon Bob
Silverman's (and others) comments. To analyze this we will have to draw
the line y=x and the curves y=Ai^X for many values of Ai. An easier way
is to use that fact that x=A^x iff ln(x)=x ln(A) (for x>0). So we draw
the curve y = ln(x) and several lines which are centered at the origin.
The easiest case first: A=1. Since ln(1) = 0 the line is horizontal,
we see that the intersection is unique and is at x=1.
For small values of x>1 (the line moves counterclockwise), we see that
the line will intersect twice. One example is sqrt(2) which intersects
at 2 and 4.
There is a point where it will be tangent to the curve. This
represents the largest A for which there will be a solution. It is
also the sup of the A's for which there are two solutions. My calc
teacher told me that it was at x=e a long time ago in a different
context. I cant see a simple proof right now, but it is confirmed by
Bob's hint. If x=e then e*lnA = 1 thus A = e^1/e.
So for A=e^1/e there is a single solution e, and for A>e^1/e there is
no solution.
Now for the A<1, There is always a single solution. But since the
other definition does not define solutions for A<y for some y<1 there
is something 'interesting' which we cannot see on this graph. What
happens is that starting from 1 and iterating leads to a loop around
the fixedpoint (When A less the y that Bob mentioned). There are two
numbers x1 and x2 such that x1=A^x2 and x2=A^x1. The plausability of
this can be seen by tracing the iterations on the graph y=A^x. (Start
at one, draw a horizontal line to the line y=x, draw a vertical line to
the curve, draw a horizontal line to y=x, ... this is just tracing out
the sequence 1, A^1, A^A^1, ...) For small enough A you can see that it
is possible to for this process to loop around the fixed point. This
is by no means a proof unless you are very carefull in drawing the
curve etc in which case you may be able to find the y that Bob
mentioned. My graphs so far are too messy to find it. (I am certian
that symbolic means are better suited to find this y).
Here is a proof sketch [ Editor: that the tangent point is at x=e ]:
Since the line is tangent, then the derivative of the curve (ln(x)) at
that point is equal to the slope of the line. The derivative at any
point is 1/x, and the slope of the line is (y2-y1)/(x2-x1) = ln(x)/x.
Set these equal and you get ln(x) = 1, therefore x = e.
-- TS (posting from shemp.CS.UCLA.EDU)
The sequence converges for all positive A such that
e^(-e) <= A <= e^(1/e) (e = 2.71828...).
[One can visualize the behaviour of the sequence {a_n} as follows:
First, pick an A > 1. Graph the curve y=A^x and the line y=x.
Now starting at the point (1,0), draw a vertical line up until you meet
the curve. Then from that point draw a horizontal line to the right
until you meet the line y=x. From there draw a line up to the curve
again, then right again to the line y=x, and so on. The sequence of
x-values of the corners of the zig-zag you are drawing is the sequence
{a_n}. Clearly, {a_n} converges if and only if the curve intersects
the line y=x.
The maximum value of A that will make such an intersection is when the
curve is tangent to the line y=x. You can solve for A in this case by
finding the point where the curve has slope=1, then equating the x- and
y-coordinates. You get A = e^(1/e).
The case where A < 1 is trickier. When you draw the zig-zag, you don't
always go up and to the right. The curve always intersects the line
y=x, but the sequence will only converge if the slope of the curve at
the intersection point is no less than -1. This occurs when
A >= e^(-e).
A rigorous, mostly analytic proof follows.]
Proof:
Case 0: A = 1.
The sequence {a_n} clearly converges to 1.
Case 1: A > 1.
Claim: The sequence {a_n} converges iff A = L^(1/L) for some L>1. (L
is the limit of {a_n}).
Proof:
Fix A > 1. Suppose the sequence converges to some L. Then L is a fixed
point of the function x |--> A^x, i.e., L = A^L. Taking the natural log
of both sides gives
ln L = L ln A
ln A = (ln L) / L
A = L^(1/L). Clearly L > 1 since A > 1.
Conversely, suppose A = L^(1/L) with L>1. We may assume, without loss
of generality, that L <= e (the function f(x) = x^(1/x) on the interval
(1, +infinity) has range (1, e^(1/e)], and reaches its maximum at x=e
(df/dx at x=e is 0), so f:(1, e] --> (1, e^(1/e)] is onto).
Define the sequence {d_n} as follows:
d_1 = -1,
d_2 = 1/L - 1,
.
.
.
d_(n+1) = L^(d_n) - 1,
.
.
.
then
a_1 = A = L^(1/L) = L^L^(-1) = L^L^(d_1),
a_2 = A^A = (L^L^(-1)) ^ (L^L^(d_1)) = L^L^( L^(d_1) - 1 ) = L^L^(d_2),
a_3 = A^A^A = (L^L^(-1)) ^ (L^L^(d_2)) = L^L^(d_3),
a_4 = L^L^(d_4),
.
.
.
That is, for any n>0, a_n = L^L^(d_n) by induction.
All the d_n are negative (also by induction), and for any x<0 and
1 < L <= e, we have (from calculus):
L^x - 1 >= e^x - 1 > x.
Thus the d_n are monotone increasing, and so converge. By continuity,
the a_n also converge. //
We've shown that the sequence {a_n} converges iff A is in the range of
f for x>1. As mentioned before, this range is the interval
(1, e^(1/e)]. Thus 1 < A <= e^(1/e). In fact, the limit of the
sequence, taken as a function of A, is the inverse of f.
Case 2: 0 < A < 1.
As in Case 1, let f(x) = x^(1/x), and fix L<1 to be such that
A = L^(1/L). (There is a unique L because f:(0,1) --> (0,1) is
one-to-one and onto). Define the sequence {d_n} as before. If we let
g(x) = L^x - 1, then d_1 = -1 and d_(n+1) = g(d_n) for any n>0.
But unlike before, the d_n now alternate between positive and negative:
d_n < 0 if n is odd,
d_n > 0 if n is even,
so we cannot use the same reasoning as before. Instead, we will split
the sequence into the positive and negative subsequences.
Claim 1: If 1/e <= L < 1, then the sequence {d_n} converges to 0. (The
sequence {a_n} then converges to L as in Case 1).
Proof:
Consider the function G(x) = g(g(x)). For any n, d_(n+2) = G(d_n). We
have, for all real x,
G(x) = L^(L^x - 1) - 1,
2
G'(x) = dG/dx = (ln L) L^( L^x - 1 + x ) > 0,
and
-ln L
G'(x) <= -----,
eL
ln (-ln L)
with equality holding at the point x = ---------- (where G''(x) = 0).
-ln L
If L >= 1/e, then G'(x) <= 1 with equality holding only at x=0 if at
all. Therefore:
x < 0 implies x < G(x) < 0,
and
x > 0 implies 0 < G(x) < x.
This means that the members of the sequence {d_(2n-1)} (n=1,2,3,...)
are all negative and monotonically increasing, and the members of the
sequence {d_2n} (n=1,2,3,...) are all positive and monotonically
decreasing. Both sequences then converge to fixed points of G, but the
only fixed point of G is 0, so both sequences converge to 0. Thus the
sequence {d_n} converges to 0. //
Claim 2: If 0 < L < 1/e, then {d_n} does not converge. In this case,
the sequences {d_2n} and {d_(2n-1)} converge to positive and negative
values, respectively.
Proof:
Define G(x) as in Claim 1. Notice that G(x) --> -1 as
x-->(-infinity), and G(x) --> 1/L - 1 as x-->(+infinity). Now if
L < 1/e, then
2
G'(0) = (ln L) > 1,
so the graph of G must intersect the line y=x at three points:
(p1,p1) for some p1, -1 < p1 < 0,
(0,0),
and (p2,p2) for some p2, 0 < p2 < 1/L - 1.
We therefore have:
x < p1 implies x < G(x) < p1,
x > p2 implies p2 < G(x) < x.
Since d_1 = -1 < p1, and d_2 = 1/L - 1 > p2, the sequence {d_(2n-1)}
increases monotonically in the interval [-1, p1), and the sequence
{d_2n} decreases monotonically in the interval (p2, 1/L - 1]. Both
sequences must converge to the fixed points, p1 and p2, respectively,
and so {d_n} does not converge. //
Claim 1 and Claim 2 imply that if L<1, {d_n} converges (and hence {a_n}
converges) iff L >= 1/e. Remembering that A = L^(1/L) gives
{a_n} converges <==> L >= 1/e <==> A >= (1/e)^e = e^(-e).
The last equivalence comes from the fact that the function
f(x) = x^(1/x) is increasing on the interval (0, 1).
QED
-- Steve Fenner <steve@gargoyle.uchicago.edu>