Numbers of the form $x^x$

I was trying to come up with a way to show that $\sum_{i=0}^{n}i^i < cn^n$, where $c$ is some positive constant.

I figured if this were true:

$\sum_{i=1}^{n-1}i^i < n^n, n>1$

in other words:

$1^1 + 2^2 + ... + (n-1)^{(n-1)} < n^n$

then the first statement must also be true (for example, when $c\ge2$).

It seems like the latter statement is true, but how can one prove it? Also, do these numbers of the form $x^x$ have a special name?

• try Googling "tetration" – Stefan Smith Feb 16 '12 at 22:28
• Some people would say $0^0=1^1$ so you might want to adjust your statements slightly – Henry Feb 16 '12 at 22:44
• @Henry : thanks, fixed that. – pepsi Feb 16 '12 at 22:52

Look at the entries before the last one. Each is less than $n^{n-1}$, and there are fewer than $n$ of them, for a total of less than $n^n$. So the whole sum is less than $2\times n^n$.
• Thank you, that's a really nice proof for the first statement. However, I was really more curious about the second statement. One can observe that $1^1+2^2 < 3^3$ and $1^1+2^2+3^3 < 4^4$. I wanted to know if this extended to all natural numbers, ie $1^1 + 2^2 + .. (n-1)^{(n-1)} < n^n$. – pepsi Feb 16 '12 at 22:48
• @pepsi Yes. Your statement is true. It can be easily proven using mathematical induction (a standard proof technique). Base case: $1^1 < 2^2$. Inductive step: Suppose that $1^1+2^2+\cdots+(k-1)^{k-1}<k^k$. Then $1^1+2^2+\cdots+(k-1)^{k-1}+k^k<k^k+k^k=2k^k\leq k\cdot k^k=k^{k+1}\leq (k+1)^{k+1}$ done. – Bill Cook Feb 16 '12 at 23:00
$1^1+2^2+...+(n-1)^{(n-1)}< (n-1)^{(n-1)}+(n-1)^{(n-1)}+...+(n-1)^{(n-1)}=(n-1)(n-1)^{(n-1)}=(n-1)^n<n^n$