Alon Amit on Quora · 2018-01-11

What is the value of ?

Oh my, what a fun question! Seriously, I have a whole new math circle plan just as a result of solving this gem. Very nice.

Despite appearances, this isn’t actually a rote calculation problem. It is designed to teach you something, if you’re attuned to its sinister machinations. Merely tackling this question may give you a glimpse of harmonic analysis, or Fourier analysis on Abelian groups, or group character theory, or DFT and digital signal processing.

Here’s the thing. You may be familiar with other, simpler sums involving binomial coefficients.

\displaystyle \sum_{k=0}^n \binom{n}{k}=2^n \tag 1

\displaystyle \sum_{k=0}^n \binom{n}{k}(-1)^k=0 \tag 2

(The second one requires n>0). Those are well-known, and have many proofs. The proof that interests us now is one you may have seen in school. It goes like this:

\displaystyle \sum_{k=0}^n \binom{n}{k}X^k = (X+1)^n \tag 3

This is just a simple instance of the binomial theorem. Now, all you have to do is substitute X=1 to get (1), while X=-1 gives you (2), immediately. Easy.

Evidently, the identity (3) is a lot more powerful than (1) and (2). It shows that we can calculate sums of binomial coefficients weighted by powers of any fixed number X (in other words, we understand a generating function, which is always a useful thing.)

However, in and of itself this doesn’t seem to be helpful here. The weights we want are

1,0,0,0,1,0,0,0,1,0,0,0,\ldots

since we wish to keep just the binomial coefficients \binom{n}{k} where k is divisible by 4. And unfortunately, there’s no X whose powers look like that.

What do we do?

Fourier transform, that’s what we do.

You see, the sequence 1,0,0,0,1,0,0,0,\ldots is not a sequence of powers of one number, yet it is periodic with a period of 4 (it’s an “impulse train” for signal processing people). If we find enough sequences of period 4 which are powers of a single number then, with luck, we may be able to combine them to yield the sequence we want.

What sequences are available to us? We have the constant sequence (“powers of 1”, or the “DC offset” in engineering parlance, or the “trivial character”)

1,1,1,1,1,1,\ldots

We have the powers of -1

1,-1,1,-1,1,-1\ldots

and of course, the only two numbers whose powers are sequences of period 4 are the imaginary units i and -i, yielding the sequences

1,i,-1,-i,1,i,-1,-i,\ldots

1,-i,-1,i,1,-i,-1,i,\ldots

And these are just what we need. We have four sequences and four constraints to satisfy (we want the period to be (1,0,0,0)), so we can do it. In fact it’s very simple: just adding together all of those Fourier sequences gives us that pulse train, times 4:

4(1,0,0,0)=(1,1,1,1)+(1,i,-1,-i)+(1,-1,1,-1)+(1,-i,-1,i)

Therefore, expanding (1+1)^n, (1+i)^n, (1-1)^n and (1-i)^n produces four weighted sums of binomial coefficients which, when added together, conspire to interfere with each other just right to leave every fourth binomial coefficient intact and eliminate everything else.

In other words, whatever n is,

\displaystyle 4\sum_{k=0}^\infty \binom{n}{4k}=(1+1)^n+(1+i)^n+(1-1)^n+(1-i)^n=2^n+(1+i)^n(1+(-i)^n)

(In the last equality we simply replace 1-i with -i(1+i) and collect like terms.)

Oh, that’s great: when n=34, or more generally when n\equiv 2\pmod 4, the last term vanishes, and we find

\displaystyle \sum_{k=0}^\infty \binom{n}{4k}=2^{n-2}

So the answer to the question is simply 2^{32}.

(I wrote the sum extending all the way to infinity, as in the question, but this is just to save a more cumbersome upper limit. The binomial coefficients simply vanish when 4k exceeds n.)

Without too much trouble we can write down simple formulas for those binomial sums for all other values of n. Furthermore, using that same method we can handle sums of binomial coefficients like \sum_k \binom{n}{4k+1}, and generally \sum_k\binom{n}{dk+e}, and…


…In fact, if you generalize what we just did, you’ll discover a wildly strong technique. We had a sequence of numbers

a_0,a_1,a_2,\ldots

which we understood well enough to recognize its generating function

f(X)=a_0+a_1X+a_2X^2+\ldots

We needed to calculate a sum of a “sampled” version of the sequence, and the way we did that was to express the sampling map

1,0,0,0,1,0,0,0,1,0,0,0,\ldots

(or any other sampling or weighting) as a linear combination of powers of a root of unity, which is simply the discrete Fourier transform. With that, we are able to express the sampled sum as a linear combination of various values f(\omega^m), where \omega is the appropriate root of unity.

The very same idea (in a multiplicative, rather than additive, context) was used by Dirichlet to estimate the number of primes in arithmetic progressions, and started an enormous and fruitful thread of ideas in mathematics.

I love how this little problem pushes us in this magnificent direction.


(Added later)

A bijective proof

The solution above is instructive, since the technique is so general. But whenever such an elegant identity shows up, one must wonder why it’s true – what is a combinatorial explanation? We’ve discovered that, when n is divisible by 4,

\displaystyle \sum_{k=0}^\infty \binom{n+2}{4k} = 2^n \tag 4

On the left we are counting sequences of 0’s and 1’s of length n+2 where the number of 1's is a multiple of 4, and on the right we are counting sequences of 0's and 1's of length n with no further constraint. Why do these two sets have the same size? There ought to be a natural bijection between them.

And indeed there is. Here’s the one I managed to find after posting this answer. There may be other, better ones.

Given any bit-string S of length n having k 1's, we can augment it to a bit-string of length n+2 with the appropriate number of 1's, as follows:

In the first three cases it is obvious that the number of 1's in the augmented string is divisible by 4: we added just the necessary number of 1's. In the last case, we couldn’t fix the number of 1's simply by attaching two bits, since there are three missing 1's. So we first flip all the bits in S, changing the number of 1's from k to n-k, and this is where it’s important that n is divisible by 4: the number of 1's now is 3 mod 4, and we can once again fix it by adding one 1. We do this by attaching 10 instead of 01, which lets us know which strings were flipped and which weren’t.

That’s important, because this is why we get a bijection. Given a long string with n+2 bits, we can reconstruct the original S: remove the last two bits, and flip the result if those last two bits were 10.

This is known as a bijective proof. It shows why the equation (4) is true by explicitly pairing up elements in two sets whose number of elements are the LHS and the RHS of the equation.

More things I should have said

The result we’ve obtained expresses the unknown magnitude as a combination

(1+1)^n+(1-1)^n+(1+i)^n+(1-i)^n

One of these is, of course, 0, but it’s a little surprising that the last two cancel out. This is actually a very deep and very general phenomenon. When such expressions come up, there’s often a leading term coming from the trivial Fourier coefficient, which is the 2^n here. The other terms tend to interfere with each other destructively. They don’t always cancel so cleanly, but when they don’t, they leave an “error term” which is much smaller than the leading term.

For example, let’s go back to the equation

\displaystyle 4\sum_{k=0}^\infty \binom{n}{4k}=2^n+(1+i)^n(1+(-i)^n)

If n is divisible by 4, let us write n=4m. We now have (1+(-i)^n)=2, and since (1+i)^4=-4, (1+i)^{4m}=(-2)^{2m}, so we get (after dividing by 4):

\displaystyle \sum_{k=0}^\infty \binom{4m}{4k}=2^{4m-2}+(-2)^{2m-1}

so there is a correction term now, but it’s like the square root of the leading term – much smaller. This is very typical of those interference/filtration/Fourier results.


Finally, test your understanding! Find a nice, explicit expression for the following infinite sum without any calculator (or even pen and paper):

\displaystyle \sum_{n=0}^\infty \frac{1}{(4n)!}.

Originally posted on Quora: https://qr.ae/pFmQtS