Average number of people required to find a pair with same birthday I have to find the expected number of people required to find a pair with same birthday. This is what I tried:
Assume that there are $M$ possible birthdays, then following the definition for expected number: 
$$E[X] = \sum_{x=2}^{x=M+1} xP[X = x] = \sum_{x=2}^{x=M+1} x \left[  \frac{M!(x-1)}{(M-x+1)! M^{x}} \right]$$
However, this is completely different from what is mentioned here as . 
$$E[X]=1+\sum_{k=1}^{M} \frac{M!}{(M-k)! M^k}.$$
Are these expressions equivalent ? How to prove it ?
 A: You can just use this formula for the expected value https://en.wikipedia.org/wiki/Expected_value#Formula_for_non-negative_random_variables
$$\operatorname{E}[X]=\sum _{k=1}^\infty \operatorname{P}(X\geq k).$$
In your case X is the random variable "first person to have a repeated birthday". We know that $$P(X\geq 1)=1$$ $$P(X\geq M+2)=0 $$ $$P(X\geq k+1)= \frac{M!}{(M-k)! M^k}$$ 
and we can easily deduce the wanted formula
$$
E[X] = 1 + \sum_{k=1}^{M} \frac{M!}{(M-k)!M^k}.
$$
A: Consider
$$
A = \sum_{x=2}^{M+1} \frac{M!x(x-1)}{(M-x+1)! M^{x}},\qquad
B=\sum_{k=1}^{M} \frac{M!}{(M-k)! M^k}.
$$
Then, using $x-1=M-(M-x+1)$ in the numerators of $A$, one gets $A=C-D$ with
$$
C= \sum_{x=2}^{M+1} \frac{M!x}{(M-x+1)! M^{x-1}},\qquad D=\sum_{x=2}^{M}\frac{M!x}{(M-x)! M^{x}}.
$$
Using $x=M+1-(M-x+1)$ in $C$ and $x=M-(M-x)$ in $D$, one gets $C=E-F$ and $D=G-H$ with
$$
E= \sum_{x=2}^{M+1} \frac{(M+1)!}{(M-x+1)! M^{x-1}},\qquad F=\sum_{x=2}^{M} \frac{M!M}{(M-x)! M^{x}},
$$
and
$$
G=\sum_{x=2}^{M}\frac{M!M}{(M-x)! M^{x}},\qquad H=\sum_{x=2}^{M-1}\frac{M!}{(M-x-1)! M^{x}}.
$$
Using $x=k+1$ in $E$ yields 
$$
E=(M+1)B.
$$
Adding the $x=1$ term in $F=G$ and using $x=k$ yields 
$$
F=G=M(B-1).
$$ 
Using $x=k-1$ in $H$ yields 
$$
H=\sum_{k=3}^{M}\frac{M!M}{(M-k)! M^{k}}=M\left(B-1-\frac{M-1}M\right)=M(B-2)+1.
$$
Thus,
$$
A=E-F-G+H=(M+1)B-2M(B-1)+M(B-2)+1=1+B.
$$
A: We can also get the second expression using linearity of expected value.
Let $X_i$ be the random variable which is $1$ if there was no pair among first $(i-1)$ persons having same birthday(which hence implies that $i$th person is needed) and $0$ otherwise.Then:
$$X = \sum_{i=1}^{M+1} X_i$$ Using linearity of expected value:
$$E[X] = \sum_{i=1}^{M+1} E[X_i] = \sum_{i=1}^{M+1} \Pr[X_i = 1]$$
Now $\Pr[X_i = 1]$ will simply be equal to the probability the we have a sequence of $(i-1)$ distinct birthdays. 
$$\Pr[X_i = 1] = \frac{M!}{(M-i+1)!M^{i-1}}$$Substituting in the above expression, we get:
$$E[X] = \sum_{i=1}^{M+1} \frac{M!}{(M-i+1)!M^{i-1}}$$
Using $k = i - 1$ and starting the sum from $i=1$ yields:
$$E[X] = 1 + \sum_{k=1}^{M} \frac{M!}{(M-k)!M^k}$$ which is the required expression.
