Compute $ \sum\limits_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ and $\sum\limits_{A,B\subseteq X} |A\cup B|$ for some given finite set $X$

Here is a systematic way to solve 2) and many other questions of the same flavor.

Principle 1: For every $E\subseteq X$, replace $\color{green}{|E|}$ by $\color{green}{\sum\limits_{x\in X}[x\in E]}$.

Here, one considers $$ \color{red}{S_X=\sum_{A\subseteq X}\sum_{B\subseteq X}|A\cup B|}, $$ and Principle 1 yields $$ S_X=\sum_{A\subseteq X}\sum_{B\subseteq X}\sum_{x\in X}[x\in A\cup B]. $$

Principle 2: Try to change the order of the summations in multiple summations, that is, replace each $\color{green}{\sum\limits_\alpha\sum\limits_\beta}$ by $\color{green}{\sum\limits_\beta\sum\limits_\alpha}$.

Here, Principle 2 yields $$ S_X=\sum_{x\in X}s_x,\qquad\text{with}\quad s_x=\sum_{A\subseteq X}\sum_{B\subseteq X}[x\in A\cup B]. $$ Now, $[x\in A\cap B]=[x\in A]+[x\in B]-[x\in A]\cdot[x\in B]$, hence $s_x=2t_x-r_x$ with $$ t_x=\sum_{A\subseteq X}[x\in A]\cdot\sum_{B\subseteq X}1=u_x\cdot v_x, $$ and $$ r_x=\sum_{A\subseteq X}[x\in A]\cdot\sum_{B\subseteq X}[x\in B]=(u_x)^2, $$ with $$ u_x=\sum_{A\subseteq X}[x\in A],\qquad v_x=\sum_{A\subseteq X}1. $$ Since $v_x$ enumerates the subsets of $X$, and $|X|=n$, one gets $v_x=2^n$ for every $x$. Since $u_x$ enumerates the subsets of $X$ which contain $x$, the collection of these is in bijection with the collection of subsets of $X\setminus\{x\}$, and $|X\setminus\{x\}|=n-1$, one gets $u_x=2^{n-1}$ for every $x$.

Thus, $t_x=2^{2n-1}$, $r_x=2^{2n-2}$ and $s_x=3\cdot2^{2n-2}$ for every $x$, and $$ \color{red}{S_X=n\cdot3\cdot4^{n-1}}. $$

$1)$ Let $$ f(x)=(1-x)^n=\sum_{k=0}^n(-1)^k\binom{n}{k}x^k\tag{1} $$ and $$g(x)=(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k\tag{2} $$ then $$ \begin{align} f(x)g(x)=(1-x^2)^n&=\sum_{k=0}^n(-1)^k\binom{n}{k}x^{2k}\tag{3}\\ &=\sum_{m=0}^n\left(\sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}\right)x^m\tag{4} \end{align} $$ where $(3)$ is simply the binomial expansion for $(1-x^2)^n$ and $(4)$ is achieved by multiplying the series in $(1)$ and $(2)$. Equating the coefficients of the powers of $x$, we get $$ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}=\left\{\begin{array}{}(-1)^{m/2}\binom{n}{m/2}&\text{when }m\text{ is even}\\0&\text{when }m\text{ is odd}\end{array}\right. $$

---

$2)$ Let $X_n=\{1,2,3,\dots,n\}$. Note that every configuration of $A\cup B$ with $A,B\subset X_{n+1}$ can be enumerated by one of $$ \begin{array}{ll} (A\cap X_n)\cup(B\cap X_n)&\text{ where }n+1\not\in A\cup B\\ (A\cap X_n)\cup(B\cap X_n)\cup\{n+1\}&\text{ where }n+1\in A\setminus B\\ (A\cap X_n)\cup(B\cap X_n)\cup\{n+1\}&\text{ where }n+1\in B\setminus A\\ (A\cap X_n)\cup(B\cap X_n)\cup\{n+1\}&\text{ where }n+1\in A\cap B\tag{5} \end{array} $$ If we let $a_n=\sum\limits_{A,B\subseteq X_n} |A\cup B|$, then using the breakdown in $(5)$, there are $2^n$ choices for $A$ and $2^n$ choices for $B$ for each addtional $\{n+1\}$. Thus, we get the recursion $$ \begin{array}{rl} a_0&=0\\ a_{n+1}&=4a_n+3\cdot4^n\tag{6} \end{array} $$ Let $a_n=4^nb_n$ and $(6)$ becomes $$ b_{n+1}=b_n+\frac34\tag{7} $$ Thus, the solution for $(6)$ and $(7)$ is $a_n=4^nb_n=4^n\cdot \frac34n$. Therefore, $$ \sum_{A,B\subseteq X_n} |A\cup B|=3n\,4^{n-1}\tag{8} $$

For the first example. Notice that it is a Cauchy product for sequences $a_k = (-1)^k \binom{n}{k}$ and $b_k = \binom{n}{k}$. Generating functions for $a$ and $b$ are $(1-x)^n$ and $(1+x)^n$ respectively. Therefore, for $0\leqslant m \leqslant 2n$: $$ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k} = [x]^m (1-x)^n (1+x)^n = [x]^m (1-x^2)^n = \left\{ \begin{array}{cl} (-1)^{m/2} \binom{n}{m/2} & m \bmod 2 =0 \\ 0 & m \bmod 2 =1 \end{array} \right. $$ If $m>2n$, the sum is zero.

For the second one, let $p$, $q$ and $r$ be sizes of disjoint sets $A \cap B^c$, $B \cap A^c$ and $A \cap B$ respectively. Then $p,q,r \geqslant 0$ and $p+q+r \leqslant n$. We first choose $p+q+r$ elements out of $n$, and then split it into 3 groups: $$ \begin{eqnarray} \sum_{A,B \subseteq X} | A \cup B | &=& \sum_{p=0}^n \sum_{q=0}^n \sum_{r=0}^n [ p+q+r \leqslant n] (p+q+r) \binom{n}{p+q+r} \binom{p+q+r}{p,q,r} \\ &=& \sum_{p=0}^n \sum_{q=0}^{n-p} \sum_{r=0}^{n-p-r} \frac{n! (p+q+r)}{(n-p-q-r)!p! q! r!} \\ &\stackrel{\text{multinomial}}{=}& \left. \left( x \frac{ \partial}{\partial x} + y \frac{\partial}{\partial y} + z \frac{\partial}{\partial z} \right) (1+x+y+z)^n \right|_{x=1,y=1,z=1} \\ &=& 3 \cdot n \cdot 4^{n-1} \end{eqnarray} $$