1
$\begingroup$

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?

  • 0
    try Googling "tetration"2012-02-16
  • 0
    Some people would say $0^0=1^1$ so you might want to adjust your statements slightly2012-02-16
  • 0
    @Henry : thanks, fixed that.2012-02-16

2 Answers 2

6

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.

  • 0
    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$.2012-02-16
  • 1
    @pepsi Yes. Your statement is true. It can be easily proven using [mathematical induction](http://en.wikipedia.org/wiki/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}. Then $1^1+2^2+\cdots+(k-1)^{k-1}+k^k done.2012-02-16
  • 1
    @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!2012-02-16
  • 0
    Thanks AndréNicolas and @BillCook. Took me awhile to see it :)2012-02-16
3

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