ちょうど \(N + k\) 回の操作で終了する場合に数え上げましょう。\(a\) は、\(0\) が \(k\) 回、\(1\) が \(N\) 回あるので \(\dbinom{N + k}{k}\) 通りです。

\(b\) は、\(a = 0\) のときだけ最低でも \(1\) 必要なのであらかじめ全体から引いておくことで、\(N + k\) 個の非負整数で総和が \(M - k\) であるものを数え上げれば良いことになり、これは \(\dbinom{N + M - 1}{N + k - 1}\) 通りです。

とこのようにともに二項係数で表せるので、あとは \(k \le M\) に渡って足し合わせればよいです。（解答終わり）

ちなみにこのまま変形していくとさらにキレイになります。

\[ \left(\mathrm{積}\right) = \frac{N + k}{N + M} \binom{N + M}{N + k} \binom{N + k}{k} = \frac{N + k}{N + M} \binom{N + M}{M} \binom{M}{k} \]

分子の分解 \(N + k\) に従って分解すると、

\[ \begin{aligned} \left(\mathrm{第1項}\right) &= \frac{N}{N + M} \binom{N + M}{M} \binom{M}{k} = \binom{N + M - 1}{N - 1} \binom{M}{k} \\ \left(\mathrm{第2項}\right) &= \frac{k}{N + M} \binom{N + M}{M} \binom{M}{k} = \frac{M}{N + M} \binom{N + M}{N} \binom{M - 1}{k - 1} = \binom{N + M - 1}{N} \binom{M - 1}{k - 1} \end{aligned} \]

となり、\(k\) に関する総和を取ると

\[ \left(\mathrm{総和}\right) = \binom{N+M - 1}{N-1}2^{M} + \binom{N+M-1}{N} 2^{M-1} \]

となります。ちなみに \(\dbinom{N+M}{N} = \dbinom{N+M - 1}{N-1} + \dbinom{N+M-1}{N}\) に注意するとこれが公式解説の結果と一致していることもわかります。