Combinatorial proof of $ \sum\limits_{k=0}^n(-1)^k\frac{2^{n-k}\binom{n}{k}}{(m+k+1)\binom{m+k}{m}}=\sum\limits_{k=0}^n\frac{\binom{n}{k}}{m+k+1}$ While answering the following question : Solution to a definite integral as $\int_0^{1}(x^{m}\left(1+x)^{n}dx\right)$, I came accross a strange identity involving  binomials.
Using the binomial theorem, we can find our first expression to that integral : $ \int_{0}^{1}{x^{m}\left(1+x\right)^{n}\,\mathrm{d}x}=\sum\limits_{k=0}^{n}{\frac{\binom{n}{k}}{m+k+1}} $, while solving it the way I did leads to another expression : $ \int_{0}^{1}{x^{m}\left(1+x\right)^{n}\,\mathrm{d}x}=\sum\limits_{k=0}^{n}{\left(-1\right)^{k}\frac{2^{n-k}\binom{n}{k}}{\left(m+k+1\right)\binom{m+k}{m}}} $.

I was wondering if we could prove, using combinatorials, that for any $ n,m\in\mathbb{N} $ : $$ \sum\limits_{k=0}^{n}{\left(-1\right)^{k}\frac{2^{n-k}\binom{n}{k}}{\left(m+k+1\right)\binom{m+k}{m}}}=\sum\limits_{k=0}^{n}{\frac{\binom{n}{k}}{m+k+1}}$$

 A: Here is an algebraic proof by way of enrichment. We seek to verify that
$$\sum_{k=0}^n (-1)^k
\frac{2^{n-k} {n\choose k}}{(m+k+1) {m+k\choose k}}
= \sum_{k=0}^n \frac{{n\choose k}}{m+k+1}.$$
We can re-write this as
$$\frac{m! n!}{(n+m+1)!} 2^n
\sum_{k=0}^n (-1)^k 2^{-k} {n+m+1\choose n-k}
= \sum_{k=0}^n \frac{{n\choose k}}{m+k+1}$$
or
$$2^n \sum_{k=0}^n (-1)^k 2^{-k} {n+m+1\choose n-k}
= (m+1) {n+m+1\choose n}
\sum_{k=0}^n \frac{{n\choose k}}{m+k+1}.$$
We get for the LHS
$$2^n \sum_{k=0}^n (-1)^k 2^{-k} {n+m+1\choose m+k+1}
= 2^n \sum_{k=0}^n (-1)^k 2^{-k} [z^{n-k}]
\frac{1}{(1-z)^{m+k+2}}
\\ = 2^n [z^n] \frac{1}{(1-z)^{m+2}}
\sum_{k=0}^n (-1)^k 2^{-k} z^k \frac{1}{(1-z)^k}.$$
Here the coefficient extractor enforces the range
and we find
$$2^n [z^n] \frac{1}{(1-z)^{m+2}}
\sum_{k\ge 0} (-1)^k 2^{-k} z^k \frac{1}{(1-z)^k}
= 2^n [z^n] \frac{1}{(1-z)^{m+2}}
\frac{1}{1+z/(1-z)/2}
\\ = [z^n] \frac{1}{(1-2z)^{m+2}}
\frac{1}{1+z/(1-2z)}
= [z^n] \frac{1}{(1-2z)^{m+1}}\frac{1}{1-z}.$$
On the other hand we have
$${n+m+1\choose n} {n\choose k}
= \frac{(n+m+1)!}{(m+1)! \times k! \times (n-k)!}
= {n+m+1\choose n-k} {m+k+1\choose m+1}$$
which gives for  the RHS
$$\sum_{k=0}^n {n+m+1\choose n-k}
\frac{m+1}{m+k+1} {m+k+1\choose m+1}
= \sum_{k=0}^n {n+m+1\choose m+k+1} {m+k\choose m}
\\ = \sum_{k=0}^n {m+k\choose m}
[z^{n-k}] \frac{1}{(1-z)^{m+k+2}}
= [z^n] \sum_{k=0}^n {m+k\choose m}
\frac{1}{(1-z)^{m+k+2}} z^k.$$
We once more have the coefficient extractor enforcing the range
and we get
$$[z^n] \frac{1}{(1-z)^{m+2}} \sum_{k\ge 0} {m+k\choose m}
\frac{1}{(1-z)^k} z^k
\\ = [z^n] \frac{1}{(1-z)^{m+2}} \frac{1}{(1-z/(1-z))^{m+1}}
= [z^n] \frac{1}{1-z} \frac{1}{(1-2z)^{m+1}}.$$
The LHS is the same as the RHS which concludes the argument. The
coeffcient extractor evaluates to
$$\bbox[5px,border:2px solid #00A000]{
\sum_{k=0}^n {k+m\choose m} 2^k.}$$
