How to evaluate this infinite series arising from a CS problem? $$\sum_{i=1}^{\infty}i\cdot((1-\frac{1}{N!})^{i-1}\cdot\frac{1}{N!})$$
where N is an integer and $N \geq 2$?
I obtained this series from the following problem:
Given a sequence of $N > 2$ unique numbers (not in sorted order), we randomly shuffle the sequence until it becomes sorted in non-decreasing order. What is the expected number of shuffles needed to sort the $N$ numbers?
Intuitively it should be $N!$ since there are $N!$ permutations, but how does one prove this formally (by evaluating the series above, for instance)?
 A: Since N is a constant, we can factor the $\dfrac1{N!}$ out. Let $r=1-\dfrac1{N!}$, so we need to compute $S=1+2r+3r^2+\cdots$. Let $X=1+r+r^2+\cdots$. Note that $X=S+rS+r^2S+\cdots=S^2$. By the geometric series formula, $S=\dfrac1{1-r}$, so $X=\dfrac1{(1-r)^2}$.  Plugging in the expression for r gives that $X=\dfrac{1}{1-\left(1-\dfrac1{N!}\right)^2}=N!^2$. Then multiplying by the $\dfrac1{N!}$ that was factored out gives the full sum as $N!$
A: To sum the series
$$ \sum_{n=1}^\infty n\cdot x^{n-1} $$
notice that it's the term-by-term derivative (with respect to $x$) of the geometric series $\sum_n x^n$, which sums to $\frac{1}{1-x}$. So the series above is the derivative of that.
However, in your case, instead of working with series, an easier approach is to say that if you get a success in the first try, then you have $1$ tries until success. Otherwise you have $1$ unsuccessful try so far and haven't made any progress at all, so the expected number of additional tries you need to make is the same as the original expectation. This gives you the equation
$$ E = 1\cdot\frac{1}{N!} + (1+E)\cdot(1-\frac{1}{N!}) $$
which is easily solved, giving $E=N!$.
