Mean of series is always less than the last element

Question

I'm working on an algorithm's efficiency and wanted to know if there was a way to show the following is true. As an example I did this with $n = 10$ and $n=4$ and it was true. I want to know if it is always true but not sure how to go about proving it.
$$n^{n-1} < \frac{\sum_{k=0}^{n} {n^k}}{n} \le n^{n}$$

Answer 1

Note that if $n>1,$ the following is true: \begin{align*} n^{n-1}&<\frac1n+1+n+n^2+\dots+n^{n-1} \\ &=\frac{n^0+n^1+n^2+\dots+n^n}{n}\\ &=\frac{\sum_{k=0}^nn^k}{n} \\ &=\frac1n\,\frac{n^{n+1}-1}{n-1}\\ &=\frac{n^n-\frac1n}{n-1} \\ &\le n^n-\frac1n \\ &\le n^n. \end{align*}

Answer 2

Provided $n>1$, you have $0<n^{k}<n^n$ for every $k<n$, so $$ n^n = \sum_{k=n}^n n^k < \sum_{k=1}^n n^k < \sum_{k=1}^n n^n = n^{n+1}, $$ and the result follows by dividing by $n$.

Indeed, the same is true for any increasing positive sequence $a_k$: $$ a_n < \sum_{k=1}^n a_k < na_n. $$

Answer 3

For $n \ge 2$.

$\frac{\sum_{k=0}^{n} {n^k}}{n}= {\sum_{k=0}^{n} {n^{k-1}}}=$

$\frac 1n + \sum_{k=0}^{n-1}n^k=$

And isn't it obvious and well known that

$n^{n-1} < n^{n-1} + \sum_{k=0}^{n-2}n^k =$

$\sum_{k=0}^{n-1}n^k < \sum_{k=0}^{n-1}n^{n-1} =$

$n*n^{n-1} = n^n$.

And that $\frac 1n < 1$.

Answer 4

Suppose $(a_k)_{k=1}^n$ is a series with $a_k \le a_{k+1}$ for $1 \le k \le n-1$. Let $A=\frac1{n}\sum_{k=1}^n a_k$ be the mean of the series.

Then $a_1 \le A \le a_n$ with equality if and only if $a_1 = a_n$.

Proof.

Since $a_k \le a_{k+1}$, then $a_j \le a_k$ for $j \le k$. In particular, for any $1 \le k \le n$, $a_1 \le a_k \le a_n$.

$\begin{array}\\ a_1-A &=a_1-\frac1{n}\sum_{k=1}^n a_k\\ &=\frac1{n}\sum_{k=1}^n (a_1-a_k)\\ &\le 0\\ \end{array}\\ $

since $a_1 \le a_k$. There is equality if and only if $a_1 = a_k$ for all $k$.

Similarly,

$\begin{array}\\ a_n-A &=a_n-\frac1{n}\sum_{k=1}^n a_k\\ &=\frac1{n}\sum_{k=1}^n (a_n-a_k)\\ &\ge 0\\ \end{array}\\ $

since $a_n \ge a_k$. There is equality if and only if $a_n = a_k$ for all $k$.