Probability with replacement, question on balls in urn. An urn contains $n$ balls numbered 1 through $n$. If you withdraw $m$ balls randomly in sequence, each time replacing the ball selected previously, find $P\{X=k\}$, $k = 1,.....m$, where $X$ is the maximum of the $m$ chosen numbers.
This was my approach
If $k$ is the maximum then all the $m$ numbers have to be chosen from $1,...k$. Now we can have $i$ balls that are less than $k$ which gives $k-1$ options and $m-i$ balls that are numbered exactly $k$ where $i$ goes from $0$ to $m-1$.
So 
$$P\{X=k\} = \sum\limits_{i=0}^{m-1}{m\choose k}\frac{(k-1)^i}{n^i}\frac{1}{n^{m-i}}$$
However the answer given is 
$$P\{X=k\} = \frac{k^m}{n^m} - \frac{(k-1)^m}{n^m}$$
I wanted to know if my approach and answer are correct, if yes how can I come to the second solution from the first one? If no, can please give the correct approach?
 A: Noting that $n^i\times n^{m-i}=n^m$ we can rewrite your sum as $$\frac 1{n^m}\times \binom mk\times \sum_{i=0}^{m-1}(k-1)^i$$  For $k=1$ this is $\frac m{n^m}$ which is not correct.
A quick approach:
It is somewhat easier to compute $P(X≤k)$.  There are $k^m$ ways to choose $m$ values $≤k$ and $n^m$ unconstrained selections, so $$P(X≤k)=\frac {k^m}{n^m}$$
But, of course, $$P(X=k)=P(X≤k)-P(X≤k-1)$$
A: Your mistake is that you did not correctly count the number of ways in which we could choose $i$ of the $m$ drawn balls to be the ones whose values are less than $k$.
That number is $\binom mi,$ but you wrote $\binom mk.$
If you write your formula with this correction, you will have
$$P\{X=k\} = \sum_{i=0}^{m-1}\binom mi\frac{(k-1)^i}{n^i}\frac{1}{n^{m-i}}.$$
This gives the correct result,
although it still takes more effort than the problem needs.
A: The following is the answer given by Sheldon Ross in A First Course in Probability.
Let $X_i$, $i = 1, ... , m$, denote the number on the $i$th ball drawn. Then
\begin{align*}
    \mathbb{P}(X\leqslant k)&=\mathbb{P}(X_{1}\leqslant k, X_{2}\leqslant k,...,X_{m}\leqslant k)\\
    &=\mathbb{P}(X_{1}\leqslant k)\mathbb{P}(X_{2}\leqslant k)\cdots\mathbb{P}(X_{m}\leqslant k)\\
    &=\left(\frac{k}{n}\right)^{m}.
\end{align*}
Therefore,
$$\mathbb{P}(X=k)=\mathbb{P}(X\leqslant k)-\mathbb{P}(X\leqslant k-1)=\left(\frac{k}{n}\right)^{m}-\left(\frac{k-1}{n}\right)^{m}.$$
