Prove that
$$\sum_{k=1}^{n+1}\binom{n+1}{k}\left(\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{k-1}\right)=2^{2n}$$
My Attempt
I was trying to find a closed form of the series $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{k-1}$
but realised that there is no closed form. So obviously i am following a wrong approach.
Noting that $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$, this can be rwritten as:
$$\sum_{0\leq j<k\leq n+1}\left(\binom{n}{k}+\binom{n}{k-1}\right)\binom{n}{j}$$
The terms $\binom{n}{i}\binom{n}{j}$ with $i\leq j$ occur once for $i=j$ and twice for $i< j$. So this can be written as:
$$\sum_{i=0}^{n}\sum_{j=0}^{n}\binom{n}{i}\binom{n}{j}=\left(\sum_{i=0}^{n}\binom{n}{i}\right)^2=2^{2n}$$
A combinatorial approach starts by noting that $2^{2n}$ is the number of ordered pairs of subsets of $\{1,2,\dots,n\}$. Given a pair $(S,T)$, we first compare their sizes.
$$(S_1,T_1)=\begin{cases}(S,T)&|S|>|T|\\ (T\cup\{0\},S)&|S|\leq |T|\end{cases}$$
Note that $|S_1|>|T_1|.$ Show that this map is one-to-one and onto the set of all $$\{(U,V)\mid U\subseteq \{0,\dots,n\},V\subseteq\{1,\dots,n\}, |U|>|V|\}$$
The left side of your equation counts this set.
The map has an obvious inverse:
$$(S,T)=\begin{cases}(S_1,T_1)&0\not\in S_1\\ (T_1,S_1\setminus\{0\})&0\in S_1\end{cases}$$