<s>[INST] If nine coins are tossed, what is the probability that the number of heads is even? If nine coins are tossed, what is the probability that the number of heads is even?
So there can either be 0 heads, 2 heads, 4 heads, 6 heads, or 8 heads.
We have $n = 9$ trials, find the probability of each $k$ for $k = 0, 2, 4, 6, 8$
$n = 9, k = 0$
$$\binom{9}{0}\bigg(\frac{1}{2}\bigg)^0\bigg(\frac{1}{2}\bigg)^{9}$$ 
$n = 9, k = 2$
$$\binom{9}{2}\bigg(\frac{1}{2}\bigg)^2\bigg(\frac{1}{2}\bigg)^{7}$$ 
$n = 9, k = 4$
$$\binom{9}{4}\bigg(\frac{1}{2}\bigg)^4\bigg(\frac{1}{2}\bigg)^{5}$$
$n = 9, k = 6$
$$\binom{9}{6}\bigg(\frac{1}{2}\bigg)^6\bigg(\frac{1}{2}\bigg)^{3}$$
$n = 9, k = 8$
$$\binom{9}{8}\bigg(\frac{1}{2}\bigg)^8\bigg(\frac{1}{2}\bigg)^{1}$$
Add all of these up: 
$$=.64$$ so there's a 64% chance of probability?
 [/INST] If $h$ denotes getting a heads and $p$ denotes getting tails, let's write $\frac{1}{2}h+\frac{1}{2}p$ for the notion of a fair coin: half the time it turns up heads, and half the time tails.
If we expand out the following product while keeping track of multiplication order,
$$\left(\frac{1}{2}h+\frac{1}{2}p\right)\left(\frac{1}{2}h+\frac{1}{2}p\right)=\frac{1}{4}hh+\frac{1}{4}hp+\frac{1}{4}ph+\frac{1}{4}pp,$$
we see that the sequences $hh$, $hp$, $ph$, and $pp$ are equally likely.  Forgetting about multiplication order, which we want to do because we only care about how many times heads or tails showed up, corresponds to just treating this like a polynomial:
$$=\frac{1}{4}h^2+\frac{1}{2}hp+\frac{1}{4}p^2.$$
We can keep multiplying copies of a fair coin together to find the probability that a certain number of heads or tails happened, where the coefficient in front of $h^kp^\ell$ is the probability of $k$ heads and $\ell$ tails.
Nine coins is the expansion
$$\left(\frac{1}{2}h+\frac{1}{2}p\right)^9=\sum_{k=0}^9\binom{9}{k}\left(\frac{1}{2}h\right)^k\left(\frac{1}{2}p\right)^{9-k}=\sum_{k=0}^9\frac{1}{2^9}\binom{9}{k}h^kp^{9-k}.$$
So far, all this has done is explain why you were adding up $2^{-9}\binom{9}{k}$ for $k=0,2,4,\dots,8$.  Here, now, is a nice trick.  If we formally set $h=1$ and $p=1$, then we get
$$1=\sum_{k=0}^9\frac{1}{2^9}\binom{9}{k},$$
and if we formally set $h=-1$ and $p=1$, then we get
$$0=\sum_{k=0}^9\frac{1}{2^9}\binom{9}{k}(-1)^k.$$
The average of these two equations is
$$\frac{1}{2}=\sum_{k=0,k\text{ even}}^9\frac{1}{2^9}\binom{9}{k},$$
since $\frac{1}{2}(1+(-1)^k)$ is $1$ or $0$ depending on whether $k$ is even or odd.  Thus the probability of an even number of heads is $\frac{1}{2}$.
Notice that this did not use the fact nine coins were tossed at any point!  (Other than the fact that at least one coin was tossed.  In the case of tossing no coins, an even number of heads happens with probability $1$.  What part of my argument goes wrong for the case of zero coins?)
</s>