Showing $\sum\limits_{j=0}^M \frac{M \choose j}{N+M \choose j} = \frac{N+M+1}{N+1}$

In an answer to another question, I stated $$\sum\limits_{j=0}^M \frac{M \choose j}{N+M \choose j} = \frac{N+M+1}{N+1}.$$

It is clearly true when $N=0$ since you add up $M+1$ copies of $1$, and when $M=0$ since you add up one copy of $1$. And, for example, with $M=4$ and $N=9$ you get $\frac{1}{1}+\frac{4}{13}+\frac{6}{78}+\frac{4}{286}+\frac{1}{715} = \frac{14}{10}$ as expected.

But how might you approach a general proof?

Solution 1:

Hint. Note that $$\frac{M \choose j}{N+M \choose j}=\frac{\binom{N+M-j}{N}}{\binom{N+M}{N}}.$$ Hence, we can rewrite the sum as $$\sum_{j=0}^M \frac{M \choose j}{N+M \choose j}=\frac{1}{\binom{N+M}{N}}\sum_{j=0}^M \binom{N+M-j}{N}=\frac{1}{\binom{N+M}{N}}\sum_{i=N}^{N+M} \binom{i}{N}.$$ Finally use the Hockey-stick identity.