# Egg dropping problem binomial coefficient recursive solution

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors) In the binomial coefficient solution we construct a function $$f(x,n)$$, which represents the maximum number of floors we can cover with $$x$$ trials and $$n$$ eggs.

So there are two cases, if we drop an egg. Either it breaks, so we have $$x-1$$ trials left and $$n-1$$ eggs, or it does not break, so we have $$x-1$$ trials left and $$n$$ eggs.

Thus we have the following recursive expression: $$f(x,n)=1+f(x-1,n)+f(x-1,n-1)$$

I cannot understand why we are adding the terms $$f(x-1,n)$$ and $$f(x-1,n-1)$$. As only one of the two contingencies happens, (the first egg breaks or not), why do we use simultaneously both terms in the sum.

Can someone please explain that in detail?

• The thing is that if the egg breaks, then you only have to cover the lower floors, as you know that it will break for all the higher floors. And if the egg doesn't break, you only have to cover the higher floors. So the floors that would get covered by $f(x-1,n)$ automatically get covered when the egg brakes, and those that would get covered by $f(x-1,n-1)$ automatically get covered when the egg doesn't brake. In both cases you can thus sum these terms. – Tassle Dec 9 '19 at 17:33