# Finite series sum I cannot figure out

I am trying to calculate the sum of a series as shown below:

$$\sum_{k=0}^x (\frac{s-k+1}{s})^n-(\frac{s-k}{s})^n$$

I have arrived here as an extension of a problem surrounding the expected number of guesses it would take for an individual to guess the birthday of any person in a group, where there are s different possible birthdays and n people in the group. Guesses cannot repeat, but more than one person may share the same birthday.

I think this series represents the odds of guessing an "occupied" birthday in the first 1,2,3... birthdays, but am having trouble getting an equation in terms of s, n, and x that states the overall chances of having guessed right after x guesses, so that I can set it equal to 0.5 and solve for x to find the expected number of guesses.

However, I am really stuck and cannot figure it out. Any help is greatly appreciated.

## 1 Answer

Let us assume $$n,x\in \mathbb{N}$$ and $$s \neq 0$$.

As it is a sum of $$x$$ summands, note that the second term of the summand (say for $$k$$) always cancels out the first term of the previous summand (for $$k-1$$). Thus overall only the first term for summand $$x$$ and the second term for $$1$$ will remain:

$$\sum_{k=0}^x (\frac{s-k+1}{s})^n-(\frac{s-k}{s})^n = (\frac{s-x+1}{s})^n-1$$

• Oh, that's it exactly. Can't believe I didn't see that sooner. Thank you so much!!! – lostinthesauce Mar 11 '19 at 0:33
• @lostinthesauce FYI, this type of series is called a Telescoping series. – John Omielan Mar 11 '19 at 2:11