Probability that number of heads flipped is divisible by 3

Question

You toss a coin n times. What is the probability that the number of heads you’ll get is divisible by 3?

(Find an exact formula, not involving sums of unbounded length; it may depend on the remainder of n modulo 6).

I believe that the problem is to find a formula for:

$$\frac{\sum\limits_{i=0}^{\lfloor n/3\rfloor} {n \choose 3i}}{2^n}$$ but I'm not really sure how to find a formula for the sum in the numerator. A hint for how to evaluate $$\sum\limits_{i=0}^{n/3} {n \choose 3i}$$ when n is divisible by three would also be much appreciated

(Note: this is not a homework problem)

Answer 1

Let $\omega $ be a primitive cube root of unit.

Hint: Consider $(1 + \omega)^n, ( 1 + \omega^2)^n, (1+1)^n$. Expand using the Binomial Theorem, and use the fact that $1 + \omega + \omega^2 = 0, \omega^3 = 1 $.

This shows that $(1 + \omega)^n+ ( 1 + \omega^2)^n+ (1+1)^n = 3 \sum { n \choose 3i} $.

Answer 2

Theorem: Let $X$ be an integer-valued random variable. $P\{n \text{ divides } X\}=\frac1n \sum_{k=0}^n \phi(2\pi k/n)$, where $\phi$ is the characteristic function of $X$. In words, this probability is the average of the probability generating function evaluated at the $n^\text{th}$ roots of unity.

I published this result in the 90's, but the proof is short. Here is an even more compact version. Let $W = \text{exp}(i\frac{2\pi X}n)$. Then $\frac1n \sum_{k=0}^n W^k = 1$if $n$ divides $X$, 0 otherwise. Hence, its expectation is the probability of the event. Apply linearity.

In your case, $X$ ~ Binomial($n$, 1/2). $\phi(t)=[(1+e^{it})/2]^n$. Eventually, we get the desired probability to be $\frac13(1+2\text{ Re }e^{i\pi n/3}/2^n)$.

Final answer to your problem: $\frac13(1+c_{n\text{ mod }6}2^{-n})$, where $(c_0,c_1,c_2,c_3,c_4,c_5)= (2,1,-1,-2,-1,1)$.