A coin is tossed $n$ times. What is the probability of getting odd number of heads?

Solution 1:

Hint. Let $p_n$ be the probability of getting an odd number of heads tossing a coin $n$ times, then $$p_{n+1}=(1-p_1)\cdot p_{n}+ p_1(1-p_{n})$$ where $p_1$ is the probability to obtain a head with one toss. So given $p_1$ (if the coin is fair then $p_1=1/2$), the above linear recursion allows us to evaluate $p_n$ for any positive integer $n$.

P.S. The recursion is explained as follows: at the $(n+1)$th toss we have an odd number of heads if and only if one of these disjoint cases occurs:

i) we have a tail and in the previous $n$ tosses there are an odd number of heads;

ii) we have a head and in the previous $n$ tosses there are an even number of heads.

Solution 2:

First toss $n-1$ times. When you toss the $n^{th}$ time, one outcome will give an even number of heads and one outcome an odd number of heads.

If the coin is a fair coin, this gives the result immediately. If it is not, then you need to combine the probabilities of odd/even after $n-1$ tosses with the probabilities on the last toss as Robert Z has done, or sum the binomial.

Solution 3:

The probability of getting $k$ heads is $\binom{n}{k}2^{-n}$. So the required probability is $$\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n}{2k+1}2^{-n}=2^{-n}\times2^{n-1}=\frac{1}{2}$$