Solve the Limit on a_n of Log^n and Pi^n(3)

[sobolev]

Can any of you solve this?

Firstly, some notation:

Let $$\Pi(x) = \Gamma(x+1)$$ where $$\Gamma(x)$$ is the usual gamma function i.e. an extension of the factorial to the complex numbers.

Let $$log^{n} (x) = log( log( \cdots log( x ) ) )$$ where $$log$$ is applied n times to x e.g. $$log^{4} (x) = log( log( log( log( x ) ) ) )$$.

Similarly, let $${\Pi}^{n} (x) = \Pi( \Pi( \cdots \Pi( x ) ) )$$ where $$\Pi$$ is applied n times to x.

THE QUESTION:
Let $$a_{n} = log^{n} ( {\Pi}^{n} (3) )$$.

Evaluate, using a computer of otherwise, $$\lim_{n \rightarrow \infty}{ a_{n} }$$ to five decimal places.

(If you are feeling especially clever try to derive a closed form expression for $$\lim_{n \rightarrow \infty}{ a_{n} }$$).

 

[sobolev]

Even just a discussion on the sort of approaches that people would take to solve such a problem would be interesting.

 

[EnumaElish]

With a computer you will soon run into overflow error (e.g. for any n > 3).

 

[rudinreader]

Did you try to throw Stirling's Approximation at it?

 

[Gib Z]

I did, but then I couldn't be bothered to find the general Approximation for iterating it n times. It's the OP's question, so he might have to bother.

 

[sobolev]

With a computer you will soon run into overflow error (e.g. for any n > 3).

Of course you will get overflow error if you compute it the naive way. The idea is to write it in a different form so you can calculate it without overflow.

I have already solved the problem. Just interested in what others have to say about it.

 

[EnumaElish]

Of course you will get overflow error if you compute it the naive way. The idea is to write it in a different form so you can calculate it without overflow.

I have already solved the problem. Just interested in what others have to say about it.

I'd really like to see a demonstration that the limit is anything other than infinity.

 

[rudinreader]

I'd really like to see a demonstration that the limit is anything other than infinity.

Yes I was trying to figure that out too. The only thing I have figured out so far is that it's monotonic increasing:

$$log^{(n)}(\Pi^{(n)}(3)) = log^{n-1}(log(\Pi^{n}(3))) \geq log^{(n-1)}(\Pi^{(n-1)}(3))$$
$$\Leftrightarrow log \Pi^{n}(3) = log \Pi^{(n-1)}(3)! \geq \Pi^{(n-1)}(3)$$
$$\Leftrightarrow \Pi^{(n-1)}(3)! \geq exp(\Pi^{(n-1)}(3))$$
$$\Leftrightarrow \Pi^{(n-1)}(3) \geq 6$$ (n! > exp(n) when n >= 6.)
$$\Leftrightarrow n \geq 2$$.

It follows that $$a_n \geq a_{n-1}$$ for n = 2,3,...
Still seems like there's a long way to go.

The following webpage was interesting, but does not seem easy to apply here, if at all possible:http://www.rskey.org/gamma.htm

 

[EnumaElish]

Actually, it should be monotonically decreasing. Which means that the limit may in fact be finite.

"Loosely," the first PI results in 4!. The first Log application converts that into the sum Log[1] + Log[2] + Log[3] + Log[4] = x < 4 (x is about 3). The second nested PI is then x!. The second nested Log turns this into Log[1] + ... + Log[x] = y < x. (y is about 2.)

So the first three terms (including n = 0) are 4 > x (approx. 3) > y (approx. 2).

 

[rudinreader]

My calculations are:
a_1 = log 3! = 1.79175946922806
a_2 = log log 3! = log log 720 = 1.88392094129494

The javascript calculator at http://www.univie.ac.at/future.media/moe/JavaCalc/jcintro.html has a "loggamma" function, I used it to compute the first three terms:
a_1 = loggamma(3+1) = 1.7917594692280545
a_2 = log(loggamma(3!+1)) = 1.8839209412949373
a_3 = log(log(loggamma(3!+1))) = 2.1161775528289275
a_4 = log(log(log(loggamma(3!+1)))) = NaN

But it seems you get stuck no matter what if you try to calculate using
log N! = log 2 + ... + log N!, because the log N! term gives NaN.

Another approach to calculating it is to set

$$s_1 = a_1$$
$$s_{n+1} = a_{n+1}-a_n$$, and consider
$$a_n = \sum_{i = 1}^n s_n$$.

So you can add term by term if you can figure out a way to calculate
$$s_n = a_n - a_{n-1} = log^{(n)}(\Pi^{(n)}(3)) - log^{(n-1)}(\Pi^{(n-1)}(3))$$
$$\ \ \ = log( \frac{ log^{(n-1)}(\Pi^{(n-1)}(3)!) }{ log^{(n-2)}(\Pi^{(n-2)}(3)!) } )$$.

Also from this expression it seems plausible that s_n -> 0 as n -> infinity, or perhaps
$$|\frac{s_{n+1}}{s_n}| \rightarrow L < 1$$ as n -> $$\infty$$, which would show a_n = sum s_n converges.

But for some reason it seems to me like the answer won't be that simple.. Actually, the root test may be better..

 

[rudinreader]

I think he's saying, for positive integers k,
$$\Pi(k) = \Gamma(k+1) = k!$$, so
$${\Pi}^{n} (3) = 3!...!$$, with n !'s.
$$log^{(n)}(\Pi^{(n)}(3)) = log^{(n)}(3!...!)$$.

 

[EnumaElish]

I think he's saying, for positive integers k,
$$\Pi(k) = \Gamma(k+1) = k!$$, so
$${\Pi}^{n} (3) = 3!...!$$, with n !'s.
$$log^{(n)}(\Pi^{(n)}(3)) = log^{(n)}(3!...!)$$.

Thanks. I started out by assuming Gamma[x] = x!, which should have been (x-1)!.

I also have been applying the (alternating) Log[PI[Log[PI...]]], which is different than Log[...Log[PI[...PI]]].

BTW, the alternating function ---> 0.

 

[sobolev]

My calculations are:
a_1 = log 3! = 1.79175946922806
a_2 = log log 3! = log log 720 = 1.88392094129494

The javascript calculator at http://www.univie.ac.at/future.media/moe/JavaCalc/jcintro.html has a "loggamma" function, I used it to compute the first three terms:
a_1 = loggamma(3+1) = 1.7917594692280545
a_2 = log(loggamma(3!+1)) = 1.8839209412949373
a_3 = log(log(loggamma(3!+1))) = 2.1161775528289275
a_4 = log(log(log(loggamma(3!+1)))) = NaN

But it seems you get stuck no matter what if you try to calculate using
log N! = log 2 + ... + log N!, because the log N! term gives NaN.

Another approach to calculating it is to set

$$s_1 = a_1$$
$$s_{n+1} = a_{n+1}-a_n$$, and consider
$$a_n = \sum_{i = 1}^n s_n$$.

So you can add term by term if you can figure out a way to calculate
$$s_n = a_n - a_{n-1} = log^{(n)}(\Pi^{(n)}(3)) - log^{(n-1)}(\Pi^{(n-1)}(3))$$
$$\ \ \ = log( \frac{ log^{(n-1)}(\Pi^{(n-1)}(3)!) }{ log^{(n-2)}(\Pi^{(n-2)}(3)!) } )$$.

I don't want to tell you how I solved the problem for a good reason. I found it to be quite interesting and I want to see other creative and unique ideas for solving it. If I tell you how I did it then I probably will not see other creative approaches.

Here is some carrot: a_4 = 2.1164259

 

[Gib Z]

Thanks for that carrot, now I can give you the answer! That is, provided I get 100 guesses.

 

[sobolev]

Okay some more carrot: a_5 = 2.1164259

Anybody solve it on their own?

 

[EnumaElish]

The Grinch in this problem is the memory overflow error (numbers too large for a desktop computer to handle).

I am thinking a statistical sampling approach.

Gamma(x) is the expected value of g(t;x) = t^x-1 where t is an exponential random variable with mean = 1 (t ~ exp(1)).

Therefore Gamma(x+1) = E[g(t;x+1)] = E[t^x].

To prevent a memory overflow error, I'd look for a way to scale t and g(t) so that E[g(h(t);x)] = E[k(x)g(t;x)] = k(x)E[g(t;x)] for some functions h and k.

E.g. let k be a scaling constant and let h(t) = t/k. Then E[g(h(t);x)] = E[g(t/k;x)] = E[t^x/k^x] = E[t^x]/k^x. Conversely, if E[t^x/k^x] = $\mu$ then E[t^x] = k^x$\mu$.

 

[sobolev]

The Grinch in this problem is the memory overflow error (numbers too large for a desktop computer to handle).

I am thinking a statistical sampling approach.

Gamma(x) is the expected value of g(t;x) = t^x-1 where t is an exponential random variable with mean = 1 (t ~ exp(1)).

Therefore Gamma(x+1) = E[g(t;x+1)] = E[t^x].

To prevent a memory overflow error, I'd look for a way to scale t and g(t) so that E[g(h(t);x)] = E[k(x)g(t;x)] = k(x)E[g(t;x)] for some functions h and k.

E.g. let k be a scaling constant and let h(t) = t/k. Then E[g(h(t);x)] = E[g(t/k;x)] = E[t^x/k^x] = E[t^x]/k^x. Conversely, if E[t^x/k^x] = $\mu$ then E[t^x] = k^x$\mu$.

Sounds interesting.

Also I would like to see how you guys would go about proving convergence of the sequence.

The one thing I couldn't do was come up with a closed form expression for the value. The person who set the problem couldn't either so I didn't waste too much time on this.

 

[rudinreader]

I may have more on this soon (or may not)... Something I was able to show that might help (or might not) is:

$$\frac{log \ log \ N!}{log \ N} \rightarrow 1$$ as $$N \rightarrow \infty$$

proof:

Use the fact that $$N \cdot log(N) - N \leq log(N!) \leq N \cdot log(N)$$,
which can be proved by showing
$$Nlog(N) - N + 1 = \int_1^N log(t) dt \leq log(N!) \leq \int_1^N log(t) + 1 \ dt = Nlog(N)$$.

You then also have to use the fact that $$lim_{M \rightarrow \infty} \frac{log(M)}{M} = 0$$ to get the limit of the log of the left side and the log of the right side:
$$\frac{log(Nlog(N) - N)}{log(N)} = \frac{log(N) + log(log(N) - 1)}{log(N)} = 1 + \frac{log(log(N) - 1)}{log(N)} \rightarrow 1 + 0 = 1$$,
$$\frac{log(Nlog(N))}{log(N)} = \frac{log(N) + log(log(N))}{log(N)} = 1 + \frac{log(log(N))}{log(N)} \rightarrow 1$$.

The claim follows by the squeeze theorem.

It seems you might be able to apply this to proving convergence as in:

$$s_n = a_n - a_{n-1} = log^{(n)}(\Pi^{(n)}(3)) - log^{(n-1)}(\Pi^{(n-1)}(3))$$
$$\ \ \ = log( \frac{ log^{(n-1)}(\Pi^{(n-1)}(3)!) }{ log^{(n-2)}(\Pi^{(n-2)}(3)!) } )$$.

Also from this expression it seems plausible that s_n -> 0 as n -> infinity...

 

[rudinreader]

Another kind of striking observation...
Let $$exp^n(x) = exp(exp(...exp(x)...))$$ (similar to log^n(x)).

For fixed k >= 1 define a sequence
$$b_n^k = exp^k(a_{n+k}) = log^n(\Pi^{n+k}(3))$$.

Notice that for any sequence c_n and any k >= 1 you have
$$c_n \rightarrow \infty$$ if and only if $$exp^k(c_n) \rightarrow \infty$$.

It follows that our sequence a_n converges if and only if $$b_n^k$$ converges for all k. In other words we can instead look at a sequence with starting value $$\Pi^{k+1}(3)$$ as large as we want. Still not sure if this is going to lead to a solution.

 

[rudinreader]

Now I have been able to show for k >= 1
$$\frac{log^{k+1}(N!)}{log^k(N)} \rightarrow 1$$ as $$N \rightarrow \infty$$

So it seems that's an inch away from proving convergence.

 

[rudinreader]

OK, the thought process above led me to the following proof that a_n converges. Since I was just looking for the first proof I could find, there perhaps are better proofs, and I didn't address the issue of computing lim a_n or perhaps finding a closed form value. (In fact I didn't "use the 3" in the a_n). If I'm lucky, there will be something in this proof that helps. Please feel free to discuss these things...

Proof that a_n converges:

Because of

It follows that our sequence a_n converges if and only if $$b_n^k$$ converges for all k.

We can can instead consider $$a_n = log^n(\Pi^n(M))$$ for any integer M > 2. (The definition doesn't work for M=1,2.)

Also use the fact (I'll omit the proof):

for k >= 1 $$\frac{log^{k+1}(N!)}{log^k(N)} \rightarrow 1$$ as $$N \rightarrow \infty$$

Another fact used is that if c_n >= 1 then log(c_n) <= c_n - 1.

Choose M such that $$\frac{log^2(N!)}{log(N!)} \leq 1 + \frac{1}{2}$$ for all N >= M, and assume log(M!) >= 2. It then follows that $$a_{n+1} \geq a_n = log^n(\Pi^n(M)) \geq 2$$ for all n >= 1, hence $$\frac{a_{n+1}}{a_n} \geq 1$$ (a_n is monotonic increasing).

We now prove by induction that for all k >= 1 $$\frac{log^{k+1}(\Pi^{k+1}(N))}{log^k(\Pi^k(N))} \leq 1 + \frac{1}{2^k}$$ whenever N >= M.
As assumed above, the result is true for k = 1. Now suppose the formula is true for k.
Then $$\frac{log^{(k+1) + 1}(\Pi^{(k+1)+1}(N))}{log^{k+1}(\Pi^{k+1}(N))} = \frac{1}{log^{k+1}(\Pi^{k+1}(N))}(log^{k+1}(\Pi^{k+1}(N)) + log^{k+2}(\Pi^{k+2}(N)) - log^{k+1}(\Pi^{k+1}(N))) = 1 + \frac{1}{log^{k+1}(\Pi^{k+1}(N))}log(\frac{log^{k+1}(\Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))})$$
...$$\leq 1 + \frac{1}{log^{k+1}(\Pi^{k+1}(N))}(\frac{log^{k+1}(\Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))} - 1) < 1 + \frac{1}{2}\frac{1}{2^k} = 1 + \frac{1}{2^{k+1}}$$.

Define s_1 = a_1, and $$s_{n+1} = a_{n+1} - a_n$$. Then $$a_n = \sum_{k=1}^n s_k$$.
We have $$s_{n+2} + ... + s_{m+n+2} = log(\frac{ log^{(n+1)}(\Pi^{(n+1)}(M!)) }{ log^n(\Pi^n(M!)))}) + ... + log(\frac{ log^{(m+n+1)}(\Pi^{(m+n+1)}(M!)) }{ log^{m+n}(\Pi^{m+n}(M!)))}) < \frac{1}{2^n} + ... + \frac{1}{2^{n+m}} < \sum_{k = n}^\infty \frac{1}{2^k} = \frac{1}{2^{n-1}}$$.

It follows that for m >= n >= 2, that $$a_m - a_n < \frac{1}{2^{n-2}}$$. Thus a_n is Cauchy, hence a_n converges.

 

[sobolev]

OK, the thought process above led me to the following proof that a_n converges. Since I was just looking for the first proof I could find, there perhaps are better proofs, and I didn't address the issue of computing lim a_n or perhaps finding a closed form value. (In fact I didn't "use the 3" in the a_n). If I'm lucky, there will be something in this proof that helps. Please feel free to discuss these things...

Proof that a_n converges:

Because ofWe can can instead consider $$a_n = log^n(\Pi^n(M))$$ for any integer M > 2. (The definition doesn't work for M=1,2.)

Also use the fact (I'll omit the proof):Another fact used is that if c_n >= 1 then log(c_n) <= c_n - 1.

Choose M such that $$\frac{log^2(N!)}{log(N!)} \leq 1 + \frac{1}{2}$$ for all N >= M, and assume log(M!) >= 2. It then follows that $$a_{n+1} \geq a_n = log^n(\Pi^n(M)) \geq 2$$ for all n >= 1, hence $$\frac{a_{n+1}}{a_n} \geq 1$$ (a_n is monotonic increasing).

We now prove by induction that for all k >= 1 $$\frac{log^{k+1}(\Pi^{k+1}(N))}{log^k(\Pi^k(N))} \leq 1 + \frac{1}{2^k}$$ whenever N >= M.
As assumed above, the result is true for k = 1. Now suppose the formula is true for k.
Then $$\frac{log^{(k+1) + 1}(\Pi^{(k+1)+1}(N))}{log^{k+1}(\Pi^{k+1}(N))} = \frac{1}{log^{k+1}(\Pi^{k+1}(N))}(log^{k+1}(\Pi^{k+1}(N)) + log^{k+2}(\Pi^{k+2}(N)) - log^{k+1}(\Pi^{k+1}(N))) = 1 + \frac{1}{log^{k+1}(\Pi^{k+1}(N))}log(\frac{log^{k+1}(\Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))})$$
...$$\leq 1 + \frac{1}{log^{k+1}(\Pi^{k+1}(N))}(\frac{log^{k+1}(\Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))} - 1) < 1 + \frac{1}{2}\frac{1}{2^k} = 1 + \frac{1}{2^{k+1}}$$.

Define s_1 = a_1, and $$s_{n+1} = a_{n+1} - a_n$$. Then $$a_n = \sum_{k=1}^n s_k$$.
We have $$s_{n+2} + ... + s_{m+n+2} = log(\frac{ log^{(n+1)}(\Pi^{(n+1)}(M!)) }{ log^n(\Pi^n(M!)))}) + ... + log(\frac{ log^{(m+n+1)}(\Pi^{(m+n+1)}(M!)) }{ log^{m+n}(\Pi^{m+n}(M!)))}) < \frac{1}{2^n} + ... + \frac{1}{2^{n+m}} < \sum_{k = n}^\infty \frac{1}{2^k} = \frac{1}{2^{n-1}}$$.

It follows that for m >= n >= 2, that $$a_m - a_n < \frac{1}{2^{n-2}}$$. Thus a_n is Cauchy, hence a_n converges.

Nicely done!

 

[sobolev]

Anybody else calculate a_4 and a_5 to verify my values?

 

[rudinreader]

Now your inductive hypothesis is:
$$\frac{log^{k+1}(\Pi^{k+1}(N))}{log^k(\Pi^k(N))} \leq 1 + \frac{1}{2^k}$$

The inductive hypothesis includes for all N >= M. (The key point is that in case k = 1 we knew that the log log N!/log N! term approached 1, so we could choose M large enough so that N >= M implied the term <= 1 + 1/2.)

So I assume that your line should be...

$$1 + \frac{1}{log^{k+1}(\Pi^{k+1}(N))}(\frac{log^{k+1}( \Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))} - 1) < 1 + \frac{1}{log^{k+1}(\Pi^{k+1}(N))}(\frac{log^{k+1}( \Pi^{k+1}(N))}{log^k(\Pi^{k}(N))} - 1) \leq 1 + \frac{1}{2}\frac{1}{2^k}$$

However the following isn't exactly clear as is implicit in the above inequality...

$$\frac{log^{k+1}( \Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))} < \frac{log^{k+1}( \Pi^{k+1}(N))}{log^k(\Pi^{k}(N))}$$

What I was getting at was $$\frac{log^{k+1}( \Pi^{k+2}(N))}{log^k(\Pi^{k+1}(N))} = \frac{log^{k+1}( \Pi^{k+1}(N!))}{log^k(\Pi^{k}(N!))}$$, whereas N! >= N >= M, so the inductive hypothesis can be applied. So the claim I was proving by induction was correct, but I probably should have at least mentioned the N >= M inside the induction proof... that was implicit from context.

 

[rudinreader]

After thinking about how to calculate a_4 I came to realize the computational approach leads to a more straightforward proof that a_n converges. That is, once you figure out how to compute a_5, you pretty much get the proof that a_n converges (because it's an increasing sequence and you get an error term on the order of 1 over k factorial).

To summarize:
Define $$a_n = log^n(\Pi^n(3))$$ as before, then we are able to compute:

a_1 = log 3! = 1.7917594692280545
a_2 = log log 3! = 1.8839209412949373
a_3 = log log log 3! = log log (loggamma(3!+1)) = 2.1161775528289275

Again, 3! is to big to compute, which implies log 3! >= 3! is hopeless to compute. So log log 3! is the best place to start.

By applying the crude inequality $$N(log(N)-1) \leq log(N!) \leq Nlog(N)$$ you can reduce log log 3! in terms of log 3! which we are able to compute (using loggamma) and you get
...log 3! + log(log(3!)-1) <= log log 3! <= log 3! + log log 3!
..which yields
...4029.5686567594484 <= log log 3! <= 4029.5689054680583, which has an error of 0.0002487086098881264.

But the point is that when you take the logarithm of the left and right hand side, that error gets diminished because log(x + e) - log(x) = log(1+e/x) <= e/x.

In this case (using the smaller term):
...log log log 3! - log(4029.5686567594484) <= 0.0002487086098881264/4029.5686567594484 = 6.172090143468014e-8
Thus
...a_4 - log log(4029.5686567594484) <= 6.172090143468014e-8/log(4029.5686567594484) = 7.434985998001389e-9.
so a_4 = log log(4029.5686567594484) = 2.1164259359607777 is within 5 decimal points.


Using an even cruder approximation (N <= log N! <= N + N(logN - 1)) and the idea above it's then very straightforward to show for k >= 4 that $$log^{k+1}\Pi^{k+1}(3) - log^k\Pi^k(3) \leq \frac{2}{\Pi^{k-3}(3)\Pi^{k-2}(3)}$$, and that's certainly a convergent sequence.

Now for k >= 5, the error is smaller than $$\frac{2}{\Pi^{2}(3)\Pi^{3}(3)}$$ and is completely negligible because the 3! term is there. The only remaining problem is the error for k = 4 (using the "crude approximation") is 2/(6*720) = 0.000462962962962963 and is not within 5 decimal places, so more modification needed..

$$log^5\Pi^5(3) - log^4\Pi^4(3) = log(\frac{log^4\Pi^5(3)}{log^3\Pi^4(3)}) \leq \frac{log^4\Pi^5(3)}{log^3\Pi^4(3)} - 1 = \frac{1}{log^3\Pi^4(3)}(log^4\Pi^5(3) - log^3\Pi^4(3)) \leq log(\frac{log^3\Pi^5(3)}{log^2\Pi^4(3)}) \leq \frac{log^3\Pi^5(3)}{log^2\Pi^4(3)} - 1$$
...$$= \frac{1}{log^2\Pi^4(3)}(log^3\Pi^5(3) - log^2\Pi^4(3)) \leq log(\frac{log^2\Pi^5(3)}{log^1\Pi^4(3)}) \leq \frac{log^2\Pi^5(3)}{log^1\Pi^4(3)} - 1 = \frac{1}{log \Pi^4(3)}(log^2\Pi^5(3)-log^1\Pi^4(3)) = \frac{1}{log \Pi^4(3)}log(\frac{log\Pi^5(3)}{\Pi^4(3)})$$
...$$\leq \frac{1}{log \Pi^4(3)}log(\frac{\Pi^4(3)log\Pi^4(3)}{\Pi^4(3)}) = \frac{log log \Pi^4(3)}{log\Pi^4(3)} \leq \frac{log\Pi^3(3) + log(log\Pi^3(3)-1)}{\Pi^3(3)(log\Pi^3(3)-1)}$$

If you stare at the last expression on the right hand side long enough, you should realize it's
...$$\leq \frac{2}{\Pi^3(3)}$$

 

[sobolev]

Nicely done rudinreader. I calculated my values using Stirling's series (in its convergent form) which was actually your first suggestion.

 

[Defennder]

Wow. This is one thread I'll definitely subscribe to. Well done rudinreader.

 

[rudinreader]

Well done rudinreader.

Thanks for the compliment... Actually recently I responded to too many questions like "what is a good analysis book" or "what is a proof", etc. and I don't want to implicitly pass myself off as an expert, because I'm really just beginning to study graduate level analysis...
But I felt like I had to at least participate in a proposed "hard problem" which was very much an analysis problem, not to establish that I'm an expert (because my solution certainly doesn't establish that), but hopefully establish that I am actually interested in Analysis! (not that anyone cares!)

My main goal these coming 6 months is actually to read through Rudin's Real and Complex Analysis .. right now I'm halfway through the chapter 2 problems.

This problem sobelev proposed required no major prerequisites but was actually harder than most (not all) of Adult Rudin problems because there was no easy hints.. (i.e. for an example of a pretty hard problem in Adult Rudin, look at problem #1 in Chapter #1. It's scary - but fortunately partial solutions are floating around the net.)

 

[sobolev]

The following is a proof of convergence. I think it is a little more transparent than rudinreader's but due credit must be given to rudinreader as his proof provides the backbone for this one.

(1) The first thing of note is...

$$\frac{ log( log( n! ) ) }{ log(n) } \rightarrow 1$$

Which rudinreader proved above and it can also be proven using Stirling's approximation.

(2) The next thing to take note of is the following...

$$\frac{ log^{k+1}(x) }{ log^{k}(y) } - 1 = \frac{ log^{k+1}(x) - log^{k}(y) }{ log^{k}(y) } = \frac{1}{log^{k}(y) } log \biggl( \frac{ log^{k}(x) }{ log^{k-1}(y) } \biggr) \leq \frac{1}{log^{k}(y)} \biggl( \frac{ log^{k}(x) }{ log^{k-1}(y) } - 1 \biggr)$$

(3) We choose n such that $$n! > 10$$ and

$$\frac{ log( log( m! ) ) }{ log(m) } \leq 1 + \frac{1}{2}$$

For all $$m \geq n$$.

Choosing such an n is always possible and this is justified by (1).

For such an n we have the following...

$$log^{k+1} \biggl( \Pi^{k+1} ( n ) \biggr) -log^k \biggl( \Pi^k ( n ) \biggr) = log \biggl( \frac{ log^{k} ( \Pi^{k+1} ( n ) ) } { log^{k-1} ( \Pi^k ( n ) ) } \biggr) \leq \frac{ log^{k} ( \Pi^{k+1} ( n ) ) } { log^{k-1} ( \Pi^k ( n ) ) } - 1$$

Now using (2)...

$$log^{k+1} \biggl( \Pi^{k+1} ( n ) \biggr) -log^k \biggl( \Pi^k ( n ) \biggr)$$

$$\leq \frac{1}{log^{k-1} ( \Pi^k ( n ) )} \biggl( \frac{ log^{k-1} ( \Pi^{k+1} ( n ) ) } { log^{k-2} ( \Pi^k ( n ) ) } - 1 \biggr)$$

$$\leq \frac{1}{log^{k-1} ( \Pi^k ( n ) ) \; log^{k-2} ( \Pi^k ( n ) )} \biggl( \frac{ log^{k-2} ( \Pi^{k+1} ( n ) ) } { log^{k-3} ( \Pi^k ( n ) ) } - 1 \biggr)$$

$$\leq \frac{1}{log^{k-1} ( \Pi^k ( n ) ) \; log^{k-2} ( \Pi^k ( n ) ) \; log^{k-3} ( \Pi^k ( n ) )} \biggl( \frac{ log^{k-3} ( \Pi^{k+1} ( n ) ) } { log^{k-4} ( \Pi^k ( n ) ) } - 1 \biggr)$$

Repeating this process we end up with...

$$log^{k+1} \biggl( \Pi^{k+1} ( n ) \biggr) -log^k \biggl( \Pi^k ( n ) \biggr) \leq \biggl( \frac{ log ( \Pi^{k+1} ( n ) ) }{ \Pi^k ( n ) } - 1 \biggr) \; \prod_{i = 1}^{k-1}{ \frac{1}{ log^{i} ( \Pi^k ( n ) ) } }$$

(4) Since $$\Pi^k (n) > n$$ for all $$k \geq 1$$ and our previously chosen n, we have

$$\frac{ log( \Pi^{k+1} (n) ) }{ \Pi^k ( n ) } = \frac{ log \biggl( \Pi( \Pi^{k} (n) ) \biggr) }{ \Pi^k ( n ) } \leq 1 + \frac{1}{2}$$

Combining this with the result from (3) we get

$$log^{k+1} \biggl( \Pi^{k+1} ( n ) \biggr) -log^k \biggl( \Pi^k ( n ) \biggr) \leq \frac{1}{2} \; \prod_{i = 1}^{k-1}{ \frac{1}{ log^{i} ( \Pi^k ( n ) ) } }$$

(5) If we let $$a_{k} = log^{k} ( \Pi^{k} (n) )$$ were n is our previosly chosen one.

Using the fact that $$x \geq 10 \Rightarrow log( \Pi( x ) ) > x$$ we get the following for all $$k \geq 1$$

$$a_{k+1} = log^{k} ( log( \Pi ( {\Pi}^{k} (n) ) ) ) > log^{k} ( {\Pi}^{k} (n) ) = a_{k}$$

Since that $${\Pi}^{k} (n) \geq \Pi(n) > 10$$.

From this we know that $$a_{k+1} > a_{k}$$, so the sequence is monotone increasing. From this we know that $$a_{k} \geq a_{1} > log(10)$$

So combining this with the result from (4) we have

$$log^{k+1} \biggl( \Pi^{k+1} ( n ) \biggr) -log^k \biggl( \Pi^k ( n ) \biggr) \leq \frac{1}{2} \; \prod_{i = 1}^{k-1}{ \frac{1}{ log^{i} ( \Pi^k ( n ) ) } } = \frac{1}{2} \; \prod_{i = 1}^{k-1}{ \frac{1}{ exp^{k-i}( a_{k} ) } } \leq \frac{1}{2} \; \prod_{i = 1}^{k-1}{ \frac{1}{ log(10) } } = \frac{1}{2 \; (log(10))^{k-1} }$$

(6) Finally putting it all together we see that...

$$a_{k} - a_{1} = \sum_{i=1}^{k-1}{ (a_{i+1} - a_{i}) } = \sum_{i=1}^{k-1}{ (log^{i+1} \biggl( \Pi^{i+1} ( n ) \biggr) -log^i \biggl( \Pi^i ( n ) \biggr)) }$$

So,
$$a_{k} - a_{1} \leq \sum_{i=1}^{k-1}{ \frac{1}{2 \; (log(10))^{i-1} } } = \frac{log(10)}{2} \; \sum_{i=1}^{k-1}{ (\frac{1}{log(10) })^{i} } = \frac{log(10)}{2} \; \frac{\frac{1}{log(10)} - (\frac{1}{log(10) })^{k}}{1 - \frac{1}{log(10) }} = \frac{log(10)}{2 ( log(10) - 1 )} \; \biggl( 1 - \frac{log(10)}{(log(10))^k } \biggr)$$

Now for $$k \geq 1$$

$$a_{k} \leq a_{1} + \frac{log(10)}{2 ( log(10) - 1 )} \; \biggl( 1 - \frac{log(10)}{(log(10))^k } \biggr) \leq a_{1} + \frac{log(10)}{2 ( log(10) - 1 )}$$

So we see that $$a_{k}$$ is a monotone inceasing sequence that is bounded from above and hence it converges.

(7) We have shown that if n satisfies certain properties stated in (3) then $$a_{k}$$ converges. Let n be such a number that satisfies the forementioned properties (given in section (3)) then it is easly demonstrateable that any larger number also satisfies those properties.

Notice that $$\lim_{k \rightarrow \infty} \Pi^{k} (3) = \infty$$ so that there exists an i such that given any n that satisfies the forementioned properties then $$\Pi^{i} (3) \geq n$$. Hence $$\Pi^{i} (3)$$ satisfies the forementioned properties and the sequence $$\{ log^{k} ( \Pi^{k} ( \Pi^{i} (3) ) ) \}_{k=1}^{\infty}$$ converges from the result in (6).

Let for $$k \geq 1$$,
$$b_{k} = log^k ( \Pi^k (3) )$$

See that,
$$b_{k+i} = log^{k+i} ( \Pi^k ( \Pi^{i} (3) ) )$$

So,
$$exp^{i}( b_{k+i} ) = log^{k} ( \Pi^k ( \Pi^{i} (3) ) )$$

So we know that $$exp^{i}( b_{k+i} )$$ converges and since $$log(x)$$ is continuous this means that $$b_{k+i}$$ and hence $$b_{k}$$ converges.

P.S. There are bound to be typing mistakes in the above.

 

[rudinreader]

It's true I used at least 1000 words in all my posts, but I just wanted to point out that the computational approach yields a single inequality that it proves it converges... You just have to play around with log(x+e)-log(x) <= e/x, and N <= log N! <= Nlog(N).

Namely, to prove a_n converges, it suffices to prove (since it shrinks pretty darn fast):
$$log^{k+1}\Pi^{k+1}(3) - log^k\Pi^k(3) \leq \frac{1}{\Pi^{k-2}(3)}$$ for k >= 3.

I left off with "you can show this with the idea above", but I will go ahead and write it out.

proof:

$$log log \Pi^{k+1}(3) - log \Pi^k(3) \leq \frac{\Pi^k(3)log(\Pi^k(3))}{\Pi^k(3)} = log \Pi^k(3)$$
$$\Rightarrow log log log \Pi^{k+1}(3) - log log \Pi^k(3) \leq \frac{log \Pi^k(3)}{log \Pi^k(3)} = 1$$
$$\Rightarrow log log log log \Pi^{k+1}(3) - log log log \Pi^k(3) \leq \frac{1}{log log \Pi^k(3)} \leq \frac{1}{\Pi^{k-2}(3)}$$.

The result follows (when you continue taking logarithms the difference gets even closer).

Edit: that last inequality on the bottom may require k >=4 or 5..
Edit#2: no it doesn't, k >= 3 works, because log 3! > 3!, and log 3! > 3!.