8
$\begingroup$

I've got a problem with deducing closed-form expressions for sums:

$1) \ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$

$2) \ \sum_{A,B\subseteq X} |A\cup B|$ where $|X|=n$

Can anyone help me?

In 1) I have no idea. I can use identity $\sum_{i=0}^{k} {n \choose i} {m \choose k-i}= {n+m \choose k}$ but I don't know if it will be useful.

In 2) I was thinking about this way: $\sum_{A,B\subseteq X} |A\cup B|=\sum_{i=0}^{n} {n \choose i}\cdot i \cdot 2^i$. Explanation: firstly I choose subset with $i$ elements. I can do this in ${ n\choose i} $ ways. It's cardinality equals $i$ and secondly I choose $2^i$ subsets of choosen subset. But it gives a wrong answer even for $n=1$.. Moreover it's still not closed-form expression..

4 Answers 4

8

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}}. $

  • 0
    Thanks for helping me see the error in my recursion.2012-03-01
5

$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} $

3

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} $

  • 0
    So this was simply a matter of a missing factor $p+q+r$ in the triple sum, after all.2012-03-02
1

An alternative view of the first problem:

$\binom{n}{k} \binom{n}{m-k}$ counts the number of ways to put a total of $k$ red marks and $m-k$ blue marks on $n$ squares, where a square can get marked more than once. Consider the operation $\phi$ which takes the first square which has exactly one mark and switches that marked color. This operation is an involution (applying it twice returns you to the same marking) and changes the parity of $k$. So each coloring $C$ where this is defined cancels out with $\phi(C)$. The only non-cancelling colorings are those where $\phi$ does nothing. This can only happen if $m$ is even, $k=m/2$, and there are $m/2$ squares marked twice.