Waste less time on Facebook — follow Brilliant.
×

Interesting Limit to Infinity Problem

\(\lim_{n\to\infty}\frac{1^{n}+2^{n}+3^{n}+...+n^{n}}{n^{n}}\)

alternatively,

\(\lim_{n\to\infty}\sum_{i=1}^n{(\frac{i}{n})}^n\)

My friends and I have been having a lot of difficulty with this particular problem. We've tried a variety of methods, such as Riemann Integration and L'Hospital's rule, but we've been unsuccessful. After plugging in large values for n we have found an extremely clean answer that we are confident in, but we still have no proof? Any ideas?

Note by Logan Dymond
4 years, 1 month ago

No vote yet
6 votes

Comments

Sort by:

Top Newest

That's a very nice problem indeed! Here's my take.

Fix any positive integer k. Then for all n>k, the sum:

\( \frac{1^n + 2^n + \ldots + n^n}{n^n} \ge \frac{(n-k)^n + (n-k+1)^n + \ldots + n^n}{n^n} = \left(1 - \frac k n\right)^n + \left(1 - \frac{k-1}n\right)^n + \ldots + 1.\) (*)

From calculus, we know that for n>k, we have \( \left(1 - \frac k n\right)^n \to e^{-k}\) as an increasing sequence in n. [ Proving that it's increasing is a bit tedious, e.g. you can replace n with a continuous variable x and differentiate with respect to x. ] So the RHS tends to \(e^{-k} + e^{-(k-1)} + \ldots + 1\) as n tends to infinity. Taking the lim inf of (*) as \(n\to\infty\) gives:

\( \lim \inf_{n\to \infty} \frac{1^n + 2^n + \ldots + n^n}{n^n} \ge 1 + e^{-1} + e^{-2} + \ldots + e^{-k}.\)

Since this holds for each k, the LHS is at least \(1 + e^{-1 } +e^{-2} + \ldots = \frac e {e-1}\).

On the other hand, for each n, we have:

\( \frac{1^n + 2^n + \ldots + n^n}{n^n} = \left(1 -\frac{n-1}n\right)^n + \left(1 - \frac{n-2}n\right)^n + \ldots + 1 \le e^{-(n-1)} + e^{-(n-2)} + \ldots + 1\)

Taking the limsup of both sides gives:

\( \lim \sup_{n\to\infty} \frac{1^n + 2^n + \ldots + n^n}{n^n} \le \lim\sup_n (e^{-(n-1)} + e^{-(n-2)} + \ldots + 1) = \frac{e}{e-1}.\)

Comparing the lim inf & lim sup of both sides should give us \( \frac e {e-1}\).

[ PS. Sorry for using lim inf and lim sup; I had wanted to apply Squeeze theorem directly, but somehow couldn't get it to work. ] C Lim · 4 years, 1 month ago

Log in to reply

@C Lim Hi sir... How did you come up with the inequality in the first statement? Christian Baldo · 4 years, 1 month ago

Log in to reply

Comment deleted Jun 12, 2013

Log in to reply

@Piyal De Applying the AM-GM inequality \[ \frac{x_1 + x_2 + \cdots + x_n}{n} \ge (x_1 x_2 \ldots x_n)^{1/n} \] with the choice \( x_i = (i/n)^n \) yields \[ \frac{1}{n} \sum_{i=1}^n \left(\frac{i}{n}\right)^n \ge \left( \prod_{i=1}^n \frac{i^n}{n^n} \right)^{1/n} = \prod_{i=1}^n \frac{i}{n} = \frac{n!}{n^n}. \] Multiplying both sides by \( n \) then gives \[ \sum_{i=1}^n \left( \frac{i}{n} \right)^n \ge \frac{n!}{n^{n-1}}, \] which tends to \( 0 \) as \( n \to \infty \). As this lower bound is looser than \( \frac{e}{e-1} \), there is no contradiction. The AM-GM inequality simply doesn't furnish a sufficiently tight bound in this case (and for those who are familiar with applying it, this fact should be evident without any calculation). Hero P. · 4 years, 1 month ago

Log in to reply

@Piyal De When you applied AM-GM, the RHS shouldn't be n!, but \( n \frac {n!}{n^n} \). C Lim · 4 years, 1 month ago

Log in to reply

@C Lim Pardon my foolishness, I was "mistaken" and thus was not "in my proper sense" then, so sorry about that................ Piyal De · 4 years, 1 month ago

Log in to reply

\( \lim_{n\to \infty}(\frac{i}{n})^n =\lim_{n\to \infty} (1 -\frac{n-i}{n})^n = e^{-(n-1)}. \)

We get:

\( \lim_{n\to \infty} \sum_{i=1}^n {(\frac{i}{n})^n} = \) \( \lim_{n\to \infty} \sum_{i=1}^n {e^{-(n-i)}} = \) \( \lim_{n\to \infty}{ \frac{e-e^{1-n}}{e-1}} = \frac{e}{e-1}. \)

---------------------------------------Q.E.D.---------------------------------------------

Is this not correct enough? Pontus Hultkrantz · 4 years, 1 month ago

Log in to reply

@Pontus Hultkrantz Your first statement does not make any sense. The answer should be independent of \(n\), indicating that your answer is wrong.

You made the mistake of claiming that

\[ \lim_{n\rightarrow \infty} (1 - \frac{f(n) } { n} ) ^n = e^{- f(n) } \]

We know that the statement is true for constants, but not necessarily for functions. For example, if \( f(n) = n \), then the expression is always 0, hence the limit is 0, and not \( e^{-n} \) whatever that is. It might be true that

\[ \lim_{n\rightarrow \infty} (1 - \frac{f(n) } { n} ) ^n = \lim_{n \rightarrow \infty} e^{- f(n) }, \]

but that will require some work too (esp if \( \lim f(n) \) does not exist). Calvin Lin Staff · 4 years, 1 month ago

Log in to reply

@Calvin Lin Thanks, good point! Pontus Hultkrantz · 4 years, 1 month ago

Log in to reply

@Pontus Hultkrantz Thematically it's quite similar to the solution provided by C L, but lacks sufficient mathematical rigor. Certainly your work vaguely suggests what the limit could be, as well as a means to prove it, but for the reasons Calvin has explained, it cannot stand as mathematically valid. One needs to be more careful--showing that the limit infimum is bounded below, in my opinion, is the critical step of C L's proof. Hero P. · 4 years, 1 month ago

Log in to reply

@Hero P. Thanks, good point! Pontus Hultkrantz · 4 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...