1
$\begingroup$

I am trying to understand the accepted answer to this question: Find: The expected number of urns that are empty

And am stuck on the part I mentioned above. I understand that:

$\sum\limits_{i=1}^n \frac{i-1}{n}=\frac{0}{n}+\frac{1}{n}+...+\frac{n-1}{n}.$ But why does this equal $\frac{n\choose2}{n}$?

I have also seen this sum solved as follows:

$\sum\limits_{i=1}^n \frac{i-1}{n}=\frac{1}{n}\sum\limits_{i=1}^n i-1=\frac{1}{n}\sum\limits_{j=0}^{n-1}j=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}$

With this method, I am having trouble seeing what exactly $j$ is and why we all of sudden entered it into the equation.

I'd appreciate if someone could shed light on either of these ways of computing the sum.

Thanks

$\endgroup$
1
  • $\begingroup$ the standard proof is by induction. $\endgroup$ Nov 16, 2013 at 0:41

2 Answers 2

4
$\begingroup$

The equation

$$\sum_{i=1}^n(i-1)=\sum_{j=0}^{n-1}j\tag{1}$$

is just a change of variable. Let $j=i-1$; then $i=j+1$, so the lefthand side of $(1)$ becomes

$$\sum_{j+1=1}^nj\;,\tag{2}$$

When $j+1=1$, clearly $j=0$, and when $j+1=n$, $j=n-1$. Thus, as $j+1$ runs from $1$ up through $n$, $j$ itself runs from $0$ up through $n-1$, and we can rewrite $(2)$ as the righthand side of $(1)$.

An alternative approach that does not involve changing the index variable is to decompose the sum:

$$\sum_{i=1}^n(i-1)=\sum_{i=1}^ni-\sum_{i=1}^n1=\frac{n(n+1)}2-n=\frac{n^2+n-2n}2=\frac{n^2-n}2=\frac{n(n-1)}2\;,$$

where the first summation uses the familiar formula for the sum of the first $n$ positive integers, and the second is just the sum of $n$ ones, or $n$.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks. I also forgot that $1+2+...+n=\frac{n(n+1)}{2}$ $\endgroup$
    – user66360
    Nov 15, 2013 at 23:49
  • $\begingroup$ @kbball: You’re welcome. $\endgroup$ Nov 15, 2013 at 23:51
2
$\begingroup$

Well, $\sum \frac{i-1}{n} = \frac{\sum (i-1)}{n} = \frac{\sum(i)-n}{n} = \frac{\frac{n\cdot(n+1)}{2}-n}{n}=\frac{\frac{n\cdot(n-1)}{2}}{n}=\frac{n-1}{2}$.

I hope this helps.

$\endgroup$
1
  • $\begingroup$ @kbball, no need for a $j$. But all they are doing is shifting the index down by $1$. $\endgroup$ Nov 15, 2013 at 23:46

You must log in to answer this question.