$\sum_{i=1}^r\sum_{j=r+1-i}^{n-r}{r \choose i}{{n-r}\choose j}=2^n-2^{n-r}+\sum_{i=1}^r\left({{n-r}\choose i}-{n\choose i}\right)$ I am trying to prove the following
$$
\sum_{i=1}^r\sum_{j=r+1-i}^{n-r}{r \choose i}{{n-r}\choose j}=2^n-2^{n-r}+\sum_{i=1}^r\left({{n-r}\choose i}-{n\choose i}\right)
$$
I want to know the hint to the correct path.
Edit
I am trying to prove this and now I got the following:
$$
-\sum_{i=1}^r \sum_{j=i}^r {r\choose i}{{n-r}\choose {j-i}}
$$
that must be equal to
$$
\sum_{i=1}^r\left({{n-r}\choose i}-{n\choose i}\right)$$
 A: We are trying to prove that
$$\sum_{p=1}^r {r\choose p}
\sum_{q=r+1-p}^{n-r} {n-r\choose q}
= 2^n - 2^{n-r}
+ \sum_{p=0}^r {n-r\choose p}
- \sum_{p=0}^r {n\choose p}.$$
We start with the LHS:
$$\sum_{p=1}^r {r\choose p}
\sum_{q=r+1-p}^{n-r} {n-r\choose n-r-q}
= [z^{n-r}] (1+z)^{n-r}
\sum_{p=1}^r {r\choose p}
\sum_{q=r+1-p}^{n-r} z^q.$$
Now the coefficient extractor enforces the upper limit of the inner sum
and we get
$$[z^{n-r}] (1+z)^{n-r}
\sum_{p=1}^r {r\choose p}
\sum_{q\ge r+1-p} z^q
= [z^{n-r}] (1+z)^{n-r} \frac{1}{1-z}
\sum_{p=1}^r {r\choose p}
z^{r+1-p}
\\ = [z^{n-2r-1}] (1+z)^{n-r} \frac{1}{1-z}
\sum_{p=1}^r {r\choose p} z^{-p}
\\ = - [z^{n-2r-1}] (1+z)^{n-r} \frac{1}{1-z}
+ [z^{n-2r-1}] (1+z)^{n-r} \frac{1}{1-z}
\left(1+\frac{1}{z}\right)^r
\\ = - [z^{n-2r-1}] (1+z)^{n-r} \frac{1}{1-z}
+ [z^{n-r-1}] (1+z)^{n} \frac{1}{1-z}.$$
Converting back into sums, we find
$$-\sum_{p=0}^{n-2r-1} {n-r\choose p}
+ \sum_{p=0}^{n-r-1} {n\choose p}
\\ = - 2^{n-r} + \sum_{p=n-2r}^{n-r} {n-r\choose p}
+ 2^n - \sum_{p=n-r}^n {n\choose p}.$$
We see that these two sums take the complete upper range of the highest
$r+1$ terms in the expansions of $(1+z)^{n-r}$ and $(1+z)^n.$ This being
binomial coefficients these sums are equal to the sums of the lower range
of the lowest $r+1$ terms by symmetry. We obtain
$$2^n - 2^{n-r}
+ \sum_{p=0}^r {n-r\choose p}
- \sum_{p=0}^r {n\choose p}$$
which is the RHS and hence the claim.
A: A straightforward combinatorial proof is also possible. Rewrite the identity as
$$\begin{align*}
&2^n-2^{n-r}=\\
&\sum_{i=1}^r\left(\binom{n}i-\binom{n-r}i\right)+\sum_{i=1}^r\sum_{j=r+1-i}^{n-r}\binom{r}i\binom{n-r}j\tag{1}
\end{align*}$$
The lefthand side is the number of subsets of $[n]$ that are not subsets of $[n]\setminus[r]$, i.e., the number of subsets of $[n]$ that intersect $[r]$.
Now fix $i\in[r]$. $\binom{n}i-\binom{n-r}i$ is the number of subsets of $[n]$ of cardinality $i$ that intersect $[r]$, and $\binom{r}i\binom{n-r}j$ is the number of subsets of $[n]$ that have $i$ members in $[r]$ and $j$ members in $[n]\setminus[r]$, where $r+1\le i+j\le n-r+i$.
Let $S$ be a subset of $[n]$ that intersects $[r]$. If $|S|\le r$, then $S$ is counted in the $i=|S|$ term of the first summation in $(1)$ and nowhere else. If $|S|>r$, let $i=|S\cap[r]|$ and $j=|S|-i$; then $S$ is counted in the $\binom{r}i\binom{n-r}j$ term of the second summation in $(1)$ and nowhere else. Thus, every subset of $[n]$ that intersects $[r]$ is counted exactly once in $(1)$, and $(1)$ is therefore equal to $2^n-2^{n-r}$.
