Can you please explain to me or give me some hints on how to prove the following identity?$$\sum^{m-1}_{k=0}\binom{n+m-1}{k} = \sum^{m-1}_{k=0}\binom{n+k-1}{k}\left(2^{m-k-1}\right)$$ where $m, n$ are positive integers.
I came across this when I was solving a problem on probability. Just for your reference, the problem, translated into English, is as follows:
A and B are two gamblers. In each round of a game, they have equal chances to win (that is, the probability of winning is 1/2). Before the game started, they had agreed that the one that wins a certain number of rounds first can get all the money (say, 1000 pounds). However, the gambling is interrupted for some reason. At this point, gambler A has to win $n$ more rounds in order to get all the money, while gambler B has to win $m$ more rounds. The question is, if it is impossible for the game to go on, how much of the 1000 pounds should be given to gamblers A and B, respectively? (The distribution of the money should be based on the probability of winning if the game had not been interrupted).
Using two different ways of thinking, we can obtain two different expressions for the probability of gambler A winning the money (had the game not been interrupted). They are:
$$\left(\frac{1}{2}\right)^n+\binom{n}{1}\left(\frac{1}{2}\right)^{n+1}+\binom{n+1}{2}\left(\frac{1}{2}\right)^{n+2}+\cdots+\binom{n+m-2}{m-1}\left(\frac{1}{2}\right)^{n+m-1}$$ and $$\left(\binom{n+m-1}{0}+\binom{n+m-1}{1}+\cdots+\binom{n+m-1}{m-1}\right)\left(\frac{1}{2}\right)^{n+m-1}$$
By comparing these two expressions, we can obtain the identity that I am asking about. I am amazed when I see these two totally different expressions which always give the same value. I am wondering if there are simple ways to transform one side into the other. If not, how can we prove this identity? Thank you for your generous help!
Simple induction on $m$ works. Indeed \begin{align} \sum_{k=0}^{m} \binom{n+m}{k} &= \sum_{k=0}^{m} \left(\binom{n+m-1}{k} + \binom{n+m-1}{k-1}\right) \\ &= \sum_{k=0}^{m} \binom{n+m-1}{k} + \sum_{k=0}^{m} \binom{n+m-1}{k-1}\\ &= \binom{n+m-1}{m} + 2 \sum_{k=0}^{m-1} \binom{n+m-1}{k} \end{align}
and
\begin{align} \sum^{m}_{k=0}\binom{n+k-1}{k}\left(2^{m+1-k-1}\right) &= \sum^{m-1}_{k=0}\binom{n+k-1}{k}\left(2^{m-k}\right) + \binom{n+m-1}{m} \\ &= \binom{n+m-1}{m} + 2 \sum_{k=0}^{m-1}\binom{n+k-1}{k}\left(2^{m-k-1}\right) \end{align}
Since for $m = 1$ the two quantities are equal to $1$.