Q&A: The Race
We never did resolve the question of which grows faster:
In this corner we have
Sequence 1 n^^n
1, 2^2, 3^3^3, 4^4^4^4, and so on.
And over here we have Sequence 2, defined recursively by
In short, we can define the second sequence as s(1) = 1; s(n) = n, followed by s(n-1) factorial signs.
Which sequence grows faster than the other??
We have many conflicting answers, and no decisive resolution; here was one idea .
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
rmjarvis said,
April 2, 2007 at 9:21 am
I guess I’ll finish my proof that I started earler, since you seem unconvinced.
Again, the trick is to take n (natural) logarithms of each element in the series. I’ll use the notation ln^n to mean n successive ln’s, much like ^^n means n successive exponents.
So the nth element in the first series becomes:
ln^n(n^^n) = ln^n(n^(n^^(n-1))) = ln^(n-1) [n^^(n-1) ln(n)]
The ln(n) factor inside the [] is _much_ less than n^^(n-1). For large values of n, which is what we care about (in fact, we are allowed to take the limit as n -> infinity), it is a very close approximation to just drop the second factor completely.
So,
ln^n(n^^n) ~= ln^(n-1)(n^^(n-1)) ~= ln^(n-2)(n^^(n-2)) ~= … ~= ln(n^^1) = ln(n)
For the second series, we need to use Stirling’s approximation for !:
n! ~= n^n e^-n sqrt(2Pi n)
So ln(n!) ~= (n+1/2) ln(n) – n (I had this a bit wrong in the previous post)
For our purposes, we can make the approximation that ln(n!) ~= n ln(n), which will be very good for the large values of n that we are considering.
Let’s use the same kind of short hand as before to write n followed by k factorials as n(!^k). Then,
ln^n(s(n)) = ln^n(n(!^s(n-1)))
~= ln^(n-1) [ n(!^(s(n-1)-1)) ln(n(!^(s(n-1)-1)) ]
Again, drop the by comparison miniscule second factor here.
~= ln^(n-1) [ n(!^(s(n-1)-1)) ]
~= ln^(n-2) [ n(!^(s(n-1)-2)) ]
….
~= n(!^(s(n-1)-n))
Since n is much less than s(n-1) for large n, taking n logs barely made almost no dent in the second series, whereas it reduced the first series all the way to just ln(n). So the second series is much larger than the first.
strauss said,
April 4, 2007 at 1:46 pm
This is correct! It’s really amazing just how much faster the second sequence grows:
Iterated ln’s really drop a number down fast, but don’t really make that much of a dent in the second sequence!
There must be a way to “visualize” this proof, i.e. explain this same idea in a way a more naive reader can get.
And this raises another question: how does the sequence compare to the staggering sequence n^^^n?
benoize said,
April 10, 2007 at 1:10 pm
Hello,
I tried to write down a proof that was a bit more rigorous, and I didn;t have the space here to do it. So I jotted it down in Latex and you can find a link to the proof here:
http://www.creativemathsolutions.nl/Proofsequence.pdf
If anyone can find mistakes (which there probably are) I would gladly hear of it!
mariano said,
April 11, 2007 at 11:24 am
I tried to analyze it in a more intuitive way, since my mathematics are not that good. Let me know if the reasoning is not correct.
Mariano from Argentina.
The series with factorial grows way faster. A way to visualize it is to define an auxiliary series.
Series A can be written as: n ^ (n ^ (n-1))
Series B can be written as: 1, 2!, 3!!, …., n followed by as many factorial operators as the previous number.
Series C (auxiliary): is n^ x where x is a number equal to the value of series B for n-1.
It’s easy to see that series C grows faster than series A as the exponent is always bigger. And series B grows faster than series C. Because for n=4, for example, we can see that 4 followed by 720 factorial operators is much bigger than 4 to the power of 720. Since 4 to the power of 720 means just 4X4X4….720 times, and 4 followed by 720 factorial operators means 4X4X4X4….719 times and then multiplied by many, many other numbers. The same can be easily visualized for any value of n. So consequently, if series C grows faster than series A and series B grows faster than series C, then series B grows faster than series A.
mariano said,
April 14, 2007 at 6:13 am
This is the same as my previous comments but expressed in more general terms, and it might be easier to visualize it. Let me know if there is something wrong.
The series with factorial grows way faster. A way to visualize it is to define an auxiliary series.
Series A can be written as: n ^ x where x = n ^ (n-1)
Series B can be written as: 1, 2!, 3!!, …., n followed by y factorial operators where y is a number equal to the value of series B for n-1
Series C (auxiliary): is n^ y where y is defined as above
It’s easy to see that series C grows faster than series A as y is always bigger than x. And series B grows faster than series C. Because n followed by y factorial operators is always bigger than n to the power of y, since n to the power of y means just n times n y number of times, and n followed by y factorial operators means n times n (y-1) number of times and then multiplied by many, many other numbers. So consequently, if series C grows faster than series A and series B grows faster than series C, then series B grows faster than series A.