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}}$$
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.}$$