We invite $N$ person to a wedding, each new guest has to sit at a friend's table or at an empty table if he has no friend. If each couple of persons $\binom{N}{2}$ has a probability $p$ to be friend, what's the expected number of tables needed?
Let's define, $\mathbf{A_i}$ : i-th person to arrive and $\mathbf{X}$ : tables needed.
That was a question in my probability exam.
First, $$\mathbb{P}\left\{ A_i \right\} = (1-p)^{i-1}$$ Thus, $$\mathbb{E}\left[ X \right] = \mathbb{E}\left[ \sum_{i=1}^{N} \mathbf{1}_{A_i} \right] = \sum_{i=1}^{N} \mathbb{E}\left[ \mathbf{1}_{A_i} \right] = \sum_{i=1}^{N} \mathbb{P}\left\{ A_i \right\} = \sum_{i=1}^{N} (1-p)^{i-1}= \sum_{i=0}^{N} (1-p)^{i}$$
Did I get the right answer? Can I simplify it? Can we write a recurrence relation? If yes, can we solve it?
Let $X_k=1$ if the $k$-th person to arrive needs a new table and $0$ otherwise; clearly
$$\Bbb E[X_k]=\Bbb P[X_k=1]=(1-p)^{k-1}\;,$$
since the $k$-th arrival needs a new table if and only if he or she is not friends with any of the previous $k-1$ arrivals. Let $X=\sum_{k=1}^NX_k$; by linearity of expectation
$$\Bbb E[X]=\sum_{k=1}^N\Bbb E[X_k]=\sum_{k=1}^N(1-p)^{k-1}=\sum_{k=0}^{N-1}(1-p)^k=\frac{1-(1-p)^N}{1-(1-p)}=\frac{1-(1-p)^N}p\;.$$
As an aside, this clearly approaches $\frac1p$ as $N$ increases.