Combinatorial proofs of the following identities I've been trying to find combinatorial proofs of the following two identities:
1: $\displaystyle\sum_{i=0}^{k} \binom{n}{i} = \sum_{i=0}^{k} \binom{n-1-i}{k-i} 2^i$ with $0 \le k \le n-1$
2: $\displaystyle\binom{2m}{2n} = \sum_{k=0}^{n} \binom{2n+1}{2k+1} \binom{m+k}{2n}$

For 1: The LHS is counting the number of subsets of size at most k from a set of size n.  The $2^i$ in the RHS makes me think of partitioning based on what elements can be considered from the full set then either including them or not, but I can't think of a way of doing this partition without overcounting and trying to interpret the binomial term hasn't helped.
For 2: Again, the LHS is simple enough but I'm lost on how to interpret the RHS.  Just from looking at it I feel like I should be considering some parity argument but haven't come up with anything else.

Any suggestions on how to proceed? Should I be looking for a more formal bijection?
 A: To get you started, here’s a HINT for the first identity: 


*

*Show that $\binom{n-1-i}{k-i}2^i$ is the number of subsets $A$ of $[n]=\{1,\ldots,n\}$ of cardinality at most $k$ such that $i+1\notin A$, and $|A\setminus[i]|=k-i$. That is $i+1$ is not in $A$, and $A$ has $k-i$ elements bigger than $i$.

*Suppose that $A\subseteq[n]$ has at most $k$ elements, and let $d=k-|A|$. Let $i$ be the largest integer such that $|[i]\setminus A|=d$. If $d=0$, for example, this means that $i+1$ is the smallest member of $[n]$ not in $A$. If $d=1$, $i+1$ is the second-smallest member of $[n]$ not in $A$. Show that such $i$ always exists. (Clearly it’s uniquely determined by $A$ if it does exist.)
I’ll have to think further about the second one.
A: Since a proof of my identity has been given, I shall give a proof which is partly combinatorial.  The combinatorial part is as follows.  For integers $a,b$ such that $a\leq b$, write $$[a,b]:=\{a,a+1,\ldots,b-1,b\}\,.$$   Consider a subset $S\subseteq [1,2m]$ of size $2n$.  There are $\dbinom{2m}{2n}$ ways to choose such subsets.  Write  $S_1:=S\cap[1,m]$ and $$S_2:=\big(S\cap[m+1,2m]\big)-m=\big\{s-m\,\big|\,s\in S\cap[m+1,2m]\big\}\,.$$
We are counting the number of subsets $S$ of $[1,2m]$ of size $2n$ with $\left|S_1\cap S_2\right|=j$ for each $j=0,1,2,\ldots,n$.
First, there are $\dbinom{m}{2n-j}$ ways to choose $S_1\cup S_2$.  Amongst the $2n-j$ chosen numbers, we can choose $S_1\cap S_2$ in $\dbinom{2n-j}{j}$ ways.  That leaves $2(n-j)$ elements each of which can either belong only in $S_1$ or only in $S_2$.  Thus, 
$$\binom{2m}{2n}=\sum_{j=0}^n\,\binom{m}{2n-j}\,\binom{2n-j}{j}\,2^{2(n-j)}\,.\tag{1}$$
We shall now prove that, for integers $M,N,K$ with $0\leq K\leq N\leq M$, we have
$$\binom{M}{N-K}=\sum_{i=0}^K\,(-1)^i\,\binom{K}{i}\,\binom{M+K-i}{N}\,.\tag{2}$$
The left-hand side is the number of ways to choose $N$ elements from $[1,M+K]$ such that every number in $[M+1,M+K]$ is selected.  The right-hand side is a direct result of the Principle of Inclusion and Exclusion, noting that $\dbinom{K}{i}$ is the number of ways to select $i$-subsets $T$ of $[M+1,M+K]$ and $\dbinom{M+K-i}{N}$ is precisely the number of ways to choose an $N$-subset of $[1,M+K]\setminus T$.
From (1) and (2), we get
$$\binom{2m}{2n}=\sum_{j=0}^n\,\sum_{i=0}^j\,(-1)^{i}\,\binom{j}{i}\,\binom{m+j-i}{2n}\,\binom{2n-j}{j}\,2^{2(n-j)}\,.$$
Let $k:=j-i$ and, by reindexing, we have
$$\binom{2m}{2n}=\sum_{k=0}^n\,\binom{m+k}{2n}\,\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}\,.$$
This is where my identity (now with a combinatorial proof---at least partially) comes in, and we are done with
$$\binom{2m}{2n}=\sum_{k=0}^n\,\binom{m+k}{2n}\,\binom{2n+1}{2k+1}\,.$$
A: Here is another variation based upon the usage of the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g.
\begin{align*}
  [z^k](1+z)^n=\binom{n}{k}
  \end{align*}

We start with (2) and obtain for $0\leq n\leq m$
  \begin{align*}
\sum_{k=2n-m}^m&\binom{2n+1}{2k+1}\binom{m+k}{2n}\tag{1}\\
&=\sum_{k=0}^{2m-2n}\binom{2n+1}{4n-2m+2k+1}\binom{2n+k}{2n}\tag{2}\\
&=\sum_{k=0}^{2m-2n}\binom{2n+1}{2m-2n-2k}\binom{-(2n+1)}{k}(-1)^k\tag{3}\\
&=\sum_{k=0}^{\infty}[z^{2m-2n-2k}](1+z)^{2n+1}[u^{k}](1+u)^{-(2n+1)}(-1)^k\tag{4}\\
&=[z^{2m-2n}](1+z)^{2n+1}\sum_{k=0}^\infty\left(-z^2\right)^k[u^k](1+u)^{-(2n+1)}\tag{5}\\
&=[z^{2m-2n}](1+z)^{2n+1}(1-z^2)^{-(2n+1)}\tag{6}\\
&=[z^{2m-2n}](1-z)^{-(2n+1)}\\
&=[z^{2m-2n}]\sum_{k=0}^\infty\binom{-(2n+1)}{k}(-z)^k\tag{7}\\
&=\binom{-(2n+1)}{2m-2n}\tag{8}\\
&=\binom{2m}{2n}\tag{9}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we sum starting from $k=2n-m$, since $\binom{m+k}{2n}=0$ for $0\leq k<2n-m$.

*In (2) we shift the index $k$ to start from zero.

*In (3) we use the binomial identities $\binom{p}{q}=\binom{p}{p-q}$ and $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

*In (4) we apply the coefficient of operator twice and extend to upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

*In (5) we use the linearity of the coefficient of operator and apply the rule $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$.

*In (6) we apply the substitution rule with $u=-z^2$
\begin{align*}
  A(z)=\sum_{k=0}^\infty a_kz^k=\sum_{k=0}^\infty z^k [u^k]A(u)
  \end{align*}

*In (7) we use the binomial series expansion

*In (8) we select the coefficient of $z^{2m-2n}$.

*In (9) we apply the identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

Using the same technique we show (1):
  \begin{align*}
  \sum_{i=0}^k\binom{n}{i}=\sum_{i=0}^k\binom{n-1-i}{k-i}2^i
  \end{align*}
We obtain
  \begin{align*}
\sum_{i=0}^k\binom{n-1-i}{k-i}2^i
&=\sum_{i=0}^\infty[z^{k-i}](1+z)^{n-1-i}2^i\\
&=[z^k](1+z)^{n-1}\sum_{i=0}^\infty\left(\frac{2z}{1+z}\right)^i\\
&=[z^k](1+z)^{n-1}\frac{1}{1-\frac{2z}{1+z}}\\
&=[z^k](1+z)^{n}\frac{1}{1-z}\\
&=[z^k]\sum_{i=0}^\infty z^i(1+z)^{n}\\
&=\sum_{i=0}^k [z^{k-i}](1+z)^{n}\\
&=\sum_{i=0}^k \binom{n}{k-i}\\
&=\sum_{i=0}^k \binom{n}{i}\\
\end{align*}
and the claim follows.

