If $n$ is a multiple of $8$, then the number of sets of size divisible by $4$ is $2^{n-2} + 2^{(n-2)/2}$

Question

Question in Cameron, Combinatorics:

If $n$ is a multiple of $8$, then the number of sets of size divisible by $4$ is $2^{n-2} + 2^{(n-2)/2}$

We are given a property derived from the Binomial theorem: For $n > 0$ , the number of subsets of an $n$-set of even and of odd cardinality are equal. Given we know that for a set $A$ with cardinality $n$, its power set has cardinality $2^n$ we can deduce that half the elements in the power set of $A$ are of even cardinality and the rest of odd, hence each is of size $2^{n-1}$

Given even sets are sets with cardinality divisible by $2$, we know $P(A_{\text{ div by 2}}) = P(A_{\text{div by 4}}) + P(A_{\text{4l+2 for some l}}) = a+b = 2^{n-1}$.

This part I understand. Now what gets me confused the the continuation of this solution, where we use the binomial theorem as so: $(1+i)^n = 2^{n/2} = \sum_{k=0}^n {n \choose k} i^k$ given $(1+i) = \sqrt 2 e^{i\pi / 4}$ and somehow we obtain $a-b = 2^{n/2}$ allowing us to find $a$.

What I do not understand, is how we can get the idea of using complex numbers to find this result. If you could detail the thinking process here, that would be much appreciated! Moreover how do we find the expression for $a-b$? I am also confused about that.

Thank you very much!

Answer 1

The standard method for solving these kinds of problems is called the 'roots of unity filter'.

In general if we have some function $f(z)$ represented as a power series $f(z)=\sum_{k\ge 0}f_kz^k$ that converges for $|z|=1$ then we may substitute the $m$ roots of unity $z=e^{2iq\pi/m}$ for $q=0,1,\ldots,m-1$ to give:

$$f(e^{2iq\pi/m})=\sum_{k\ge 0}f_ke^{2iqk\pi/m}$$

then summing over $q$ gives:

$$\sum_{q=0}^{m-1}f(e^{2iq\pi/m})=\sum_{k\ge 0}f_k\left(\sum_{q=0}^{m-1}e^{2iqk\pi/m}\right)\tag{1}$$

Looking at the inner sum on the right $\sum_{q=0}^{m-1}e^{2iqk\pi/m}$ we see that the common ratio of this finite geometric series is $e^{2ik\pi/m}$ which is $1$ iff $m| k$ and, in this case, the sum is simply $m$. Otherwise the sum is $(1-e^{2ik\pi})/(1-e^{2i\pi/m})=0$ as $e^{2ik\pi}=1$ and the denominator is non-zero. So:

$$\sum_{q=0}^{m-1}e^{2iqk\pi/m}=\begin{cases}m & m| k\\0 &\text{otherwise}\end{cases}$$

therefore $(1)$ becomes:

$$\begin{align}\sum_{q=0}^{m-1}f(e^{2iq\pi/m})&=\sum_{k\ge 0}f_{km}m\\ \implies \sum_{k\ge 0}f_{km}&=\frac{1}{m}\sum_{q=0}^{m-1}f(e^{2iq\pi/m})\tag{2}\end{align}$$

This is our master formula.

For the specific case of selecting subsets with size a multiple of $4$ from an $n$ element set we want the sum $\sum_{k\ge 0}f_{km}=\sum_{k\ge 0}\binom{n}{4k}$ so here $m=4$ and the function must be $f(z)=(1+z)^n$. Using $(2)$ then gives us:

$$\sum_{k=0}^{n}\binom{n}{4k}=\frac{1}{4}((1+1)^n+(1+i)^n+(1-i)^n)$$

but if $n$ is a multiple of $8$ then, since $1+i=\sqrt{2}e^{i\pi/4}$ and $1-i=\sqrt{2}e^{-i\pi/4}$, we have $(1+i)^n=(1-i)^n=2^{n/2}$ and therefore

$$\begin{align}\sum_{k\ge 0}\binom{n}{4k}&=\frac{1}{4}(2^n+2\cdot 2^{n/2})\\[2ex]&=2^{n-2}+2^{(n-2)/2}\tag{Answer}\end{align}$$

as required.

I hope this gives a more coherent and general method than suggested in the question.

Answer 2

Let $A_2$ be the number of subsets with size divisible by 2, and $A_4$ the number with size divisible by 4. Let $B$ be the number with size divisible by 2 but not 4. You have established that $A_2=A_4+B=2^{n-1}$.

Using the binomial theorem we have $$2^{n/2}=(1+i)^{n}=\sum_{k=0}^n{n\choose k}i^k=\sum_{k=0\bmod4}+\sum_{k=1\bmod4}+\sum_{k=2\bmod4}+\sum_{k=3\bmod4}$$ The real part of the rhs is $$\sum_{k=0\bmod4}+\sum_{k=2\bmod4}=A_4-B$$ because the terms in $\sum_{k=0\bmod4}$ have $i^4=1$ whereas the terms in $\sum_{k=2\bmod4}$ have $i^2=-1$.

As to how anyone thought of using complex numbers, the idea was to find some way of distinguishing the various types of term. Since $i^4=1$ it is not surprising that it can be made to work.