Probability that number of heads flipped is divisible by 3 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)
 A: 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} $.
A: 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)$.
