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.

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that

$\displaystyle \sum_{k=0}^{n} {n \choose k} = (1 + 1)^n$

while

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

It follows that

$\displaystyle \sum_{k=0}^{n/2} {n \choose 2k} = 2^{n-1}$.

A direct combinatorial proof is as follows: fix an element $s \in S$. If a given subset has $s$ in it, add it in; otherwise, take it out. This defines a bijection between the number of subsets with an even number of elements and the number of subsets with an odd number of elements.

The analogous formulas for the subsets with a number of elements divisible by $3$ or $4$ are more complicated, and divide into cases depending on the residue of $n \bmod 6$ and $n \bmod 8$, respectively. The algebraic derivations of these formulas are as follows (with $\omega$ a primitive third root of unity): observe that

$\displaystyle \sum_{k=0}^{n} \omega^k {n \choose k} = (1 + \omega)^n = (-\omega^2)^n$

while

$\displaystyle \sum_{k=0}^{n} \omega^{2k} {n \choose k} = (1 + \omega^2)^n = (-\omega)^n$

and that $1 + \omega^k + \omega^{2k} = 0$ if $k$ is not divisible by $3$ and equals $3$ otherwise. (This is a special case of the discrete Fourier transform.) It follows that

$\displaystyle \sum_{k=0}^{n/3} {n \choose 3k} = \frac{2^n + (-\omega)^n + (-\omega)^{2n}}{3}.$

$-\omega$ and $-\omega^2$ are sixth roots of unity, so this formula splits into six cases (or maybe three). Similar observations about fourth roots of unity show that

$\displaystyle \sum_{k=0}^{n/4} {n \choose 4k} = \frac{2^n + (1+i)^n + (1-i)^n}{4}$

where $1+i = \sqrt{2} e^{ \frac{\pi i}{4} }$ is a scalar multiple of an eighth root of unity, so this formula splits into eight cases (or maybe four).

Question: Does anyone know a direct combinatorial proof of these identities?

share|improve this question
    
related: math.stackexchange.com/questions/1382/… –  Grigory M Aug 2 '10 at 10:48
1  
    
Does this have anything to do with it? –  Michael Hardy May 22 at 18:09

2 Answers 2

up vote 8 down vote accepted

Fix two elements s1,s2∈S and divide subsets of S into two parts (subsets of S containing only s2)∪(subsets of S which contains s1 if they contain s2). The second part contains equal number of sets for all reminders mod 3 (because Z/3 acts there adding s1, then s2, then removing both of them) -- namely, 2n-2. And for the first part we have a bijection with subsets (edit: with 2 mod 3 elements) of a set with (n-2) elements.

So we get a recurrence relation that gives an answer 2n-2+2n-4+... -- i.e. (2n-1):3 for even and (2n-2):3 for odd n.


Errata. For n=0,1,5 mod 6 one should add "+1" to the answer from the previous paragraph (e.g. for n=6 the correct answer is 1+20+1=22 and not 21).

Let me try to rephrase the solution to make it obvious. For n=2k divide S on k pairs and consider an action of a group Z/3Z on each pair described in a first paragraph. We get an action of (Z/3Z)k on subsets of S, and after removal of it's only fixed point (k-element set consisting of second points from each pair) we get a bijection between subsets which have 0, 1 or 2 elements mod 3. So there are (2n-1):3 sets with i mod 3 elements excluding the fixed point and to count that point one should add "+1" for i=k mod 3.

And for n=2k+1 there are 2 fixed points — including or not (2k+1)-th element of S — with k+1 and k elements respectively.

share|improve this answer
    
Thanks! That's easier than I thought it would be. I'll accept this answer, but if you get ideas about the 4 case I'd certainly still be interested in hearing them. –  Qiaochu Yuan Jul 29 '10 at 7:41
    
I'll certainly try to think about "4 case". And looks like in "3 case" there is more than meets an eye: in the solution we identify subsets of S (|S|=2k) with P^1(Z/3)^k and consider an action of (Z/3)^k on it; and the only fixed point of the action gives "-1" in the formula. Probably I should think more about this situation. Thanks for the question! –  Grigory M Jul 29 '10 at 11:55
    
cf. artofproblemsolving.com/Forum/… (link via @Qiaochu Yuan's comment to another question) –  Grigory M Aug 25 '10 at 17:45
    
ah, thanks. I have to admit I never checked either of those solutions... –  Qiaochu Yuan Aug 25 '10 at 19:42

There's a very pretty combinatorial proof of the general identity $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$ for $\omega$ a primitive $r$th root of unity, in Benjamin, Chen, and Kindred, "Sums of Evenly Spaced Binomial Coefficients," Mathematics Magazine 83 (5), pp. 370-373, December 2010.

They show that both sides count the number of closed $n$-walks on $C_r$ beginning at vertex 0, where $C_r$ is the directed cycle on $r$ elements with the addition of a loop at each vertex, and a walk is closed if it ends where it starts.

Left-hand side: In order for an $n$-walk to be closed, it has to take $kr$ forward moves and $n-kr$ stationary moves for some $k$.

Right-hand side: The number of closed walks starting at vertex $j$ is the same regardless of the choice of $j$, and so it suffices to prove that the total number of closed $n$-walks on $C_r$ is $\sum_{j=0}^{r-1} (1+\omega^j)^n.$ For each $n$-walk with initial vertex $j$, assign each forward step a weight of $\omega^j$ and each stationary step a weight of $1$. Define the weight of an $n$-walk itself to be the product of the weights of the steps in the walk. Thus the sum of the weights of all $n$-walks starting at $j$ is $(1+\omega^j)^n$, and $\sum_{j=0}^{r-1} (1+\omega^j)^n$ gives the total weight of all $n$-walks on $C_r$. The open $n$-walks can then be partitioned into orbits such that the sum of the weights of the walks in each orbit is $0$. Thus the open $n$-walks contribute a total of $0$ to the sum $\sum_{j=0}^{r-1} (1+\omega^j)^n$. Since a closed $n$-walk has weight $1$, $\sum_{j=0}^{r-1} (1+\omega^j)^n$ must therefore give the number of closed $n$-walks on $C_r$.


They then make a slight modification of the argument above to give a combinatorial proof of $$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$ where $0 \leq a < r$.


Benjamin and Scott, in "Third and Fourth Binomial Coefficients" (Fibonacci Quarterly, 49 (2), pp. 99-101, May 2011) give different combinatorial arguments for the specific cases you're asking about, $\sum_{k \geq 0} \binom{n}{3k}$ and $\sum_{k \geq 0} \binom{n}{4k}$. I prefer the more general argument above, though, so I'll just leave this one as a link and not summarize it.

share|improve this answer

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.