A double sum with combinatorial factors Let $n$, $p$ and $j$ be integers. As a byproduct of some other calculations I have discovered  the following identity:
\begin{equation}
\sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} \binom{j}{p_1} \binom{2n-j}{j-p} \binom{n-j+p}{1+p+p_1} (-1)^p = \frac{1}{2} \binom{2n}{2j+1}
\end{equation}
I used Mathematica to check that it holds true. The problem is how do I go about proving it?
 A: This is not going to be a complete answer but since this approach seems to me intuitive i will show it. This is a sort of ``by induction proof''. Let us look at the lhs for the biggest possible $j$ and then go down in $j$. We hope to see a pattern as a function of $j$ and thus guess the result. 
So we take $j=n-1$.We have:
\begin{equation}
S(j=n-1)= \sum\limits_{p=0}^{n-1} \sum\limits_{p_1=0}^{n-1} \binom{p+p_1}{p_1} \binom{n-1}{p_1} \binom{n+1}{n-1-p} \binom{1+p}{1+p+p_1}
\end{equation}
Since the last binomial factor on the right equals $\delta_{p_1,0}$, we have:
\begin{equation}
S(j=n-1)= \sum\limits_{p=2}^{n+1} \binom{n+1}{p} (-1)^p = \frac{1}{2} \binom{2 n}{1} = rhs
\end{equation}
Now we take $j=n-2$.We have:
\begin{equation}
S(j=n-2)= \sum\limits_{p=0}^{n-2} \sum\limits_{p_1=0}^{n-2} \binom{p+p_1}{p_1} \binom{n-2}{p_1} \binom{n+2}{n-2-p} \binom{2+p}{1+p+p_1}
\end{equation}
Since the last binomial factor on the rhs equals $\delta_{p_1,0} (2+p) + \delta_{p_1,1}$ we have:
\begin{equation}
S(j=n-2)= \sum\limits_{p=4}^{n+2} \binom{n+2}{p}\left[(p-2) + (p-3)(n-2)\right](-1)^p = \frac{1}{2} \binom{2n}{3} = rhs
\end{equation}
Now we take $j=n-3$. We have:
\begin{equation}
S(j=n-3)= \sum\limits_{p=0}^{n-3} \sum\limits_{p_1=0}^{n-3} \binom{p+p_1}{p_1} \binom{n-3}{p_1} \binom{n+3}{n-3-p} \binom{3+p}{1+p+p_1}
\end{equation}
Since the last binomial factor on the rhs equals $\delta_{p_1,0} \binom{p+3}{2} + \delta_{p_1,1} \binom{p+3}{1} + \delta_{p_1,2}$ we have:
\begin{align}
S(j=n-3)
&= \sum\limits_{p=6}^{n+3} \binom{n+3}{p}\Big[\binom{p-3}{2} 
+ \binom{p-3}{1}(p-5)(n-3) \\& \hspace{3cm} + \binom{p-4}{2} \binom{n-3}{2}\Big](-1)^p = \frac{1}{2} \binom{2n}{5} = rhs
\end{align}
As we go down in $j$ we always do the sum over $p_1$ using properties of the delat function and we end up with a couple of sums over $p$ each of which are elementary. The only thing that remains is to write down all those sums and compute them. Yet, since the pattern has already emerged I quit at this stage..
