Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
Thanks for helping me see the error in my recursion. –  robjohn Mar 1 '12 at 1:36
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
I believe that you are missing a $(-1)^{m/2}$ in your first answer. –  robjohn Mar 2 '12 at 14:31
    
@robjohn Indeed. Thank you for checking this. I corrected the post now. –  Sasha Mar 2 '12 at 15:15
    
much better :-) (+1) –  robjohn Mar 2 '12 at 15:30
    
So this was simply a matter of a missing factor $p+q+r$ in the triple sum, after all. –  Did Mar 2 '12 at 18:12
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.