# 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

## 2 Answers

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$.

That seems to be the proof you had in mind, though the phrasing "if this were true" does not make the logic of the argument clear.

-
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
@pepsi: That's exactly what the first two sentences of the post prove. The same thing has been done, with symbols, in the answer by Eraldo. If you really want a formal proof by induction, it has been given by Bill Cook above. However, the idea is so simple that I think formal induction is superfluous. Unless, of course, a homework exercise insists that you use formal induction! –  André Nicolas Feb 16 '12 at 23:07
Thanks AndréNicolas and @BillCook. Took me awhile to see it :) –  pepsi Feb 16 '12 at 23:12

Well, try the following:

$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$

-