Expectation for the MLE for a Uniform Discrete Random Variable $\newcommand{\szdp}[1]{\!\left(#1\right)} \newcommand{\szdb}[1]{\!\left[#1\right]}$
Problem Statement: Suppose that $n$ integers are drawn at random and with replacement from the integers $1,2,\dots,N.$ Find the maximum-likelihood estimator $\hat{N}$ of $N,$ and show that $E\!\left(\hat{N}\right)$ is approximately $[n/(n+1)]N.$
Note: This is essentially Exercise 9.88a,b from Mathematical Statistics with Applications, 5th. Ed., by Wackerly, Mendenhall, and Sheaffer.
My Work So Far: Let $Y_1, Y_2,\dots,Y_n$ be the random sample. The distribution function is
$$p(y)=
\begin{cases}
1/N,&y\in\{1,2,\dots,N\}\\
0,&\text{otherwise.}
\end{cases}
$$
Hence, the likelihood function is
$$L=\frac{1}{N^n}.$$
It is clear that the logarithmic differentiation approach will not work, here. Instead, we need to choose the smallest value of $N$ that is still greater than all the $Y_i.$ That means $\hat{N}=Y_{(n)}=\max(Y_1, Y_2,\dots,Y_n),$ the maximum order statistic.
The cumulative distribution is just
$$F(y_i)=P(Y_i\le y_i)=y_i/N.$$
Following the wikipedia page on order statistics based on discrete distributions, we construct the three probabilities:
\begin{align*}
p_1
&=P(Y_i<x)\\
&=F(x)-p(x)\\
&=x/N-1/N\\
&=(x-1)/N\\
p_2
&=P(Y_i=x)\\
&=p(x)\\
&=1/N\\
p_3
&=P(Y_i>x)\\
&=1-F(x)\\
&=1-x/N.
\end{align*}
It follows, then, that
\begin{align*}
P(Y_{(n)}\le x)
&=(p_1+p_2)^n\\
&=\szdp{\frac{x-1}{N}+\frac1N}^{\!\!n}\\
&=\szdp{\frac{x}{N}}^{\!n}\\
P(Y_{(n)}<x)
&=p_1^n\\
&=\szdp{\frac{x-1}{N}}^{\!\!n}\\
P(Y_{(n)}=x)
&=P(Y_{(n)}\le x)-P(Y_{(n)}<x)\\
&=\szdp{\frac{x}{N}}^{\!n}-\szdp{\frac{x-1}{N}}^{\!\!n}\\
&=\frac{x^n-(x-1)^n}{N^n}\\
E\szdp{\hat{N}_2}
&=\frac{1}{N^n}\sum_{x=1}^N x\szdb{x^n-(x-1)^n}
\end{align*}
My Question: It's not the least bit obvious where to go from here. The exact sum is intractable unless I want to write it in terms of harmonic numbers (I think $N^{n+1}-H_{N-1}^{(-n)}$ is correct). The problem did say to find an approximate expectation, but there are usually dozens of ways to approximate things. Which approximation method would get me towards the stated goal?
 A: I can replicate your result by computing the mean as
$$E[Y_{n}] = \sum_{y=1}^N P(Y_n \geq y) =  \sum_{y=1}^N 1-\left( \frac{y-1}{N}\right)^n = N - \frac{1}{N^n} \sum_{y=0}^{N-1} y^n = N - \frac{H^{(-n)}_{N-1}}{N^n}$$
Then, if you approximate the generalized harmonic number with an integral
$$\sum_{y=0}^{N-1}y^n \approx \int_0^{N-1}y^n dy = \frac{1}{n+1}(N-1)^{n+1}$$
You get $$\begin{array}{}
E[Y_n]&\approx& N - \frac{1}{n+1} \frac{(N-1)^{n+1}}{N^n} \\
&\approx& \frac{N^{n+1}}{N^n} -  \frac{\frac{1}{n+1}\sum_{k=0}^{n+1} {{n+1}\choose{k}}(-1)^{k}N^{n+1-k}}{N^n}\\
&\approx& \frac{N^{n+1}}{N^n} -  \frac{\frac{1}{n+1}N^{n+1}+\sum_{k=1}^{n+1} {{n+1}\choose{k}}(-1)^{k}N^{n+1-k}}{N^n}\\
&\approx& N \frac{n}{n+1}  - N \frac{1}{n+1}  \sum_{k=1}^n {{n+1}\choose{k}}\frac{1}{(-N)^{-k}}  &\approx& N \frac{n}{n+1} 
\end{array}$$
You would get to this more direct when you integrate till $N$ in which case the integral is $\frac{1}{n+1}N^{n+1}$

Alternative
The draw from a discrete uniform distribution is like the draw from a continuous uniform distribution but rounding the figure up. So you can use the order distribution for a sample drawn from a continuous uniform distribution as an estimate.
The order distribution for a sample drawn from a continuous uniform distribution is a beta distribution, $Beta(n,1)$, which has the mean $\frac{n}{n+1}$. Scaling the range from $(0,1)$ to $(0,N)$ adds another factor $N$ giving you $E[Y_n] \approx N \frac{n}{n+1}$

Lower estimate
So the estimate $E[Y_n] \approx N \frac{n}{n+1}$ stems from either one of the following:

*

*using the estimate of the generalized harmonic number $$\sum_{y=0}^{N}y^n \approx \int_0^{N}y^n dy = \frac{1}{n+1}(N)^{n+1}$$ which overestimates the generalized harmonic number and underestimates the expectation $E[Y_n]$


*estimating the uniform discrete distribution with the uniform continuous distribution but rounding the figures up to achieve the discrete distribution. (this means that the continuous distribution has a lower value than the discrete distribution) So, also from this point of view we can see that the estimate underestimates the expectation $E[Y_n]$.
If we would use a uniform continuous distribution, but round down, then this will be like using the uniform distribution from $1$ to $N+1$ instead of from $0$ to $N$ and the upper estimate is $N \frac{n}{n+1} + 1$
