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?

  • $\begingroup$ try Googling "tetration" $\endgroup$ – Stefan Smith Feb 16 '12 at 22:28
  • $\begingroup$ Some people would say $0^0=1^1$ so you might want to adjust your statements slightly $\endgroup$ – Henry Feb 16 '12 at 22:44
  • $\begingroup$ @Henry : thanks, fixed that. $\endgroup$ – 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$.

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.

  • $\begingroup$ 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$. $\endgroup$ – pepsi Feb 16 '12 at 22:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Cook Feb 16 '12 at 23:00
  • 1
    $\begingroup$ @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! $\endgroup$ – André Nicolas Feb 16 '12 at 23:07
  • $\begingroup$ Thanks AndréNicolas and @BillCook. Took me awhile to see it :) $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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