I am stumped on a problem:
A coin with $p${h} = $p = 1-q$ is tossed n times. Show that the probability that the number of heads is even equals $0.5[1+(q-p)^n]$.
From the assumption, we know that is coin is an unfair coin with different probabilities for heads and tails (otherwise $p-q$ would always be zero). I figured the best way to show this would be through induction, but so far I'm stumped when it comes to the $(n+1)$ case.
It is trivial to show that when $n=1$ we get $p${even} = $q$. So, with that step is taken care of we assume true for $n$ and prove $n+1$. However, I'm not sure what to do when I get to the $(n+1)^{th}$ step. That is:
$$0.5[1+(q-p)^{n+1}]$$
Thank you in advanced for all your help, I really appreciate it!
Hint:
Let $r_{n}$ denote the probability that by $n$ tosses the number of heads is even.
Then: $$r_{0}=1$$ and: $$r_{n+1}=qr_{n}+p\left(1-r_{n}\right)$$
Based on these equations by induction you can prove that: $$r_{n}=\frac{1}{2}\left[1+\left(q-p\right)^{n}\right]$$