71*. a) Banach's problem ${ }^{1}$. A person simultaneously bought two boxes of matches and put them in his pocket. After that, every time he needed to light a match, he randomly took one or the other box. After some time, upon emptying one of the boxes, the person discovered that it was empty. What is the probability that at this moment the second box still contained $k$ matches, if the number of matches in the unopened box was $n$?

b) Using the result from part a), find the value of the sum

$$
C_{2 n}^{n}+2 C_{2 n-1}^{n}+4 C_{2 n-2}^{n}+\ldots+2^{n} C_{n}^{n}
$$

Note. Another method for finding this sum is given in the solution to problem 55.
71. a) At the moment when a person discovers that the matchbox taken out of the pocket is empty, the second box can contain 0 matches (i.e., be also empty), 1 match, 2 matches, 3 matches, and so on up to \( n \) matches inclusive. The considered experiment consists of the person repeatedly drawing one match at random from the first or the second box until one of the boxes is empty. In different outcomes of the experiment, the total number of matches drawn will naturally be different; therefore, different outcomes will not be equally probable and cannot be used to calculate probabilities. This difficulty can be overcome by a method similar to the one we used above in solving problem 65: we will assume that when the drawn box turns out to be empty, the person refills it (practically, this can be achieved, for example, by replacing the empty box with a new full one) and continues to draw matches at random from one or the other box. We agree to consider that this sequential drawing of matches stops after the \((2n+1)\)-th match is drawn; since initially there were a total of \(2n\) matches in both boxes, it is clear that by this moment at least one of the boxes will be found empty (and will be refilled again). Now we can rephrase the given problem as follows: a certain person draws a match from one of two boxes \(2n+1\) times in a row, with each time the probability of drawing a match from one or the other box being the same. The number of matches in each box can be considered unlimited (since we agreed to refill an empty box again). At some point, the person draws the \((n+1)\)-th match from one of the boxes (in the original formulation, this would mean that he found the box empty); what is the probability that by this moment \(n-k\) matches have been drawn from the second box?

In the new formulation, the problem is solved quite simply. Each separate draw can, obviously, have two outcomes (a match can be drawn from the first or the second box); \(2n+1\) sequential draws can have \(2^{2n+1}\) different outcomes. This is the total number of equally probable outcomes of the considered experiment. Favorable outcomes are those in which out of the first \(2n-k\) draws, \(n\) matches are drawn from the first box and \(n-k\) from the second, and the \((2n-k+1)\)-th match is again drawn from the first box, or, conversely, out of the first \(2n-k\) draws, \(n\) are made from the second box, \(n-k\) from the first, and the \((2n-k+1)\)-th draw is also from the second; the results of the last \(k\) draws can be anything. But the number of outcomes of \(2n-k\) draws in which \(n\) matches are drawn from the first box and \(n-k\) from the second is equal to the number of combinations \(C_{2n-k}^{n}\) of \(2n-k\) elements taken \(n\) at a time. Combining these outcomes with the \(2^k\) possible outcomes of the last \(k\) trials, we find that the number of outcomes in which \(n+1\) matches are first drawn from the first box, and by this moment \(n-k\) matches have been drawn from the second box, is \(C_{2n-k}^{n} \cdot 2^k\). Exactly the same number of outcomes will be those in which the \((n+1)\)-th match is first drawn from the second box, and by this moment \(n-k\) matches have been drawn from the first box. Thus, the total number of favorable outcomes of the experiment here is \(2 C_{2n-k}^{n} \cdot 2^k = 2^{k+1} C_{2n-k}^{n}\). From this, the formula for the desired probability is

\[
p = \frac{2^{k+1} C_{2n-k}^{n}}{2^{2n+1}} = \frac{C_{2n-k}^{n}}{2^{2n-k}}
\]

b) At the moment when the person mentioned in the condition of part (a) discovers that the matchbox he took out is empty, the second box can contain any number of matches from 0 to \( n \). The sum of the probabilities that this number is 0, that it is 1, that it is 2, and so on up to \( n \), obviously, should equal one: by summing all these probabilities, we get a fraction where both the numerator and the denominator contain the total number of equally probable outcomes of the experiment. Thus,

\[
\frac{C_{2n}^{n}}{2^{2n}} + \frac{C_{2n-1}^{n}}{2^{2n-1}} + \frac{C_{2n-2}^{n}}{2^{2n-2}} + \ldots + \frac{C_{n}^{n}}{2^n} = 1
\]

Therefore,

\[
C_{2n}^{n} + 2 C_{2n-1}^{n} + 2^2 C_{2n-2}^{n} + \ldots + 2^n C_{n}^{n} = 2^{2n}
\]