Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For each $n$, define $f_n:\mathbb R^+\rightarrow \mathbb R^+$ by $f_n(x) = \underbrace{x^{x^{x^{...^{x^x}}}}}_n$

I want to find a function $f:\mathbb R^+\rightarrow \mathbb R^+$ such that for any given $n$, $f$ is eventually greater than $f_n$.

Here $\mathbb R^+$ means the non-negative reals.

share|improve this question
    
Note that $\underbrace{x^{x^{x^\dots}}}_n=^n\!\!x$ –  ᴊ ᴀ s ᴏ ɴ Sep 5 '12 at 13:10
    
see also en.wikipedia.org/wiki/Tetration and note that andres answer is like tetration of a number with itself, kind of like how squaring is multiplication of a number with itself –  binn Sep 5 '12 at 13:14

1 Answer 1

up vote 19 down vote accepted

To make notation smoother, write $f(n,x)$ for $f_n(x)$. Let $$f(x)=f(\lceil x\rceil, x).$$ Here $\lceil x\rceil$ is the "ceiling" function that gives the smallest integer $\ge x$.

Remark: This is a typical "diagonalization" argument. Basically the same idea seems to have been first used by du Bois-Reymond to deal with orders of growth of functions. He did it a few years before Cantor used diagonalization in Set Theory.

share|improve this answer
2  
I don't follow, what is $f(x,x)$? –  fretty Sep 5 '12 at 12:56
2  
@AdamRubinson: It does not depend on $n$. It is given explicitly in terms of $x$. –  André Nicolas Sep 5 '12 at 13:01
3  
@AdamRubinson: No, the function does not depend on $n$. (It is defined in terms of the $f_n$s, but the function itself is independent of $n$. For instance, for $10 \le x \le 11$, we have $g(x) = f_{10}(x)$, and for $20 \le x \le 21$, we have $g(x) = f_{20}(x)$, etc. But the function $g$ does not depend on $n$.) –  ShreevatsaR Sep 5 '12 at 13:03
3  
@AdamRubinson: Here is a similar problem: find a function that eventually grows faster than any $x^n$. Solution: Let $g(x)=x^{\lceil x\rceil}$. Exactly the same idea. –  André Nicolas Sep 5 '12 at 13:08
2  
@AdamRubinson: To solve the problem of majorizing the $x^n$, the familiar $e^x$ will do. I was just using the $x^{\lceil x\rceil}$ to illustrate the idea of the main proof in a simpler setting. –  André Nicolas Sep 5 '12 at 16:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.