Mean of series is always less than the last element 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}$$
 A: 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*}
A: 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. $$
A: 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$.
A: 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$.
