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.


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$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.