Proof sought for a sum involving binomials that simplifies to 1/2 A proof of:
$$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$
Conjecture based on the following Maple code:
Q := (1/2)^(2*m+1) * sum( binomial(m, k) * sum(binomial(m+1, j), j = 0 .. k), k = 0 .. m):
simplify([seq(Q, m = 1 .. 20, 1)]);

[1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2]

 A: Since ${a\choose b} = {a\choose a-b}$, we have
\begin{align*}
\sum_{k = 0}^m{m\choose k}\sum_{j = 0}^k{m+1\choose j} &= \sum_{k = 0}^m{m\choose m-k}\sum_{j = 0}^k{m+1\choose m+1-j} \\
& = \sum_{r = 0}^m{m\choose r} \sum_{s = r+1}^{m+1}{m+1\choose s}
\end{align*}
where the last line follows by putting $r = m-k$ and $s = m+1-j$. If you add both sides together you get $2^{2m+1} = 2\times 2^{2m}$, so your result is true.
A: Suppose we seek to verify that
$$\sum_{k=0}^m {m\choose k}
\sum_{j=0}^k {m+1\choose j} = 2^{2m}.$$
We use the integral
$${m+1\choose j} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{j+1}} \; dz.$$
This yields for the inner sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} 
\sum_{j=0}^k \frac{1}{z^j}\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} 
\frac{1/z^{k+1}-1}{1/z-1}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^{m+1}
\frac{1/z^{k+1}-1}{1-z}\; dz.$$
Now the second term in the difference  does not have a pole at zero so
we are left with
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{k+1}} \frac{1}{1-z} \; dz.$$
This yields for the remaining sum the integral
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} \frac{1}{1-z} 
\sum_{k=0}^m {m\choose k} \frac{1}{z^k} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z} \frac{1}{1-z} 
\left(1+\frac{1}{z}\right)^m \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2m+1}}{z^{m+1}} \frac{1}{1-z} \; dz.$$
Extracting the residue we find
$$\sum_{q=0}^m {2m+1\choose q} =
\frac{1}{2} \times 2^{2m+1} = 2^{2m},$$
as claimed.
