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


I started this chapter sometimes ago and faced in front of a tough problem. At first I started considering cases. Case-I : The probability of getting 1 head.Case-II : The probability of getting 3 head and so on. But there are many cases. So how can I solved this . Please help me. Thank you!
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.
If $X$ is the number of heads you have to calculate
$$P(X \text{ is odd})=\sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}P(X=2k+1).$$

As $X\sim Binomial(n,1/2)$, you can calculate that probability for each $k$. That is:
$$P(X \text{ is odd})=\sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}{n \choose 2k+1}\left(\frac12\right)^{2k+1} \left(\frac12\right)^{n-(2k+1)} =\left(\frac12\right)^n \sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}{n \choose 2k+1}.$$

Now, if $n$ is odd the last sum is
$${n \choose 1}+{n \choose 3}+\cdots+{n \choose n-2}+{n \choose n},$$
which by the symmetry of the binomial coefficients is equal to 
$${n \choose n-1}+{n \choose n-3}+\cdots+{n \choose 2}+{n \choose 0}.$$

Since it is known that
$${n \choose 0}+{n \choose 1}+{n \choose 2}+\cdots+{n \choose n-1}+{n \choose n}=2^n,$$
then both previous sums add up to $\tfrac{2^n}2=2^{n-1}$.

On the other hand, if $n$ is even the sum is
$${n \choose 1}+{n \choose 3}+\cdots+{n \choose n-1}=$$
$$=\left[{n-1 \choose 0} + {n-1 \choose 1}\right] + \left[{n-1 \choose 2} + {n-1 \choose 3}\right]+\cdots+\left[{n-1 \choose n-2}+{n-1 \choose n-1}\right]=$$
$$=2^{n-1},$$
as in the '$n$ is odd' case.

So for every $n \in \mathbb{N}$
$$P(X \text{ is odd})=\left(\frac12\right)^n \cdot 2^{n-1}= \frac12.$$