Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
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
1  
@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  
@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
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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