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