Show that $P_n=p(1-P_{n-1})+(1-p)P_{n-1}$ $n \ge 1$

Question

Independent trials that result in a success with probability p and a failure with probability 1-p are called Bernoulli trials. Let $P_n$ denote the probability that n Bernoulli trials result in an even number of success (0 being considered an even number). Show that $P_n=p(1-P_{n-1})+(1-p)P_{n-1}$ $n \ge 1$ and use this to prove (by induction) that $P_n=\frac{1+(1-2p)^n}{2}$

So $P_n$ denotes the probability that n Bernoulli trials result in an even number of successes p = probability of success p-1 = probability of failure

$P_n=p(1-P_{n-1})+(1-p)P_{n-1}$ $n \ge 1$

I can see that the first part of the equation is the probability of success multiplied by the probability that n-1 trials result in failure, plus the probability of failure multiplied by probability that n-1 trials result in success.

But I don;t know how to show this mathematically..

So I think for the second part, for induction I need to start with the base case, n=1: $$P_n=p(1-P_{n-1})+(1-p)P_{n-1}$$ $$P_1=p(1-P_{1-1})+(1-p)P_{1-1}$$ $$P_0=p(1-P_{0})+(1-p)P_{0}$$

Then I get kind of stuck, well..$P_0$ is probability of n=0 trials, so would that be 0? $$P_0=p(1)=0$$

Then for induction, I need to show that n+1 is true right?

Answer 1

For the first part: We want to have have an even number of total successes. Lets say that we have performed $n-1$ trials. If we then have an odd number of successes, we will need the last trial to be a success in order for the total number of successes to be even. If the number of successes after $n-1$ trials is already even, then the last event should not be a success. So:

$ P_n=(1-P_{n-1})*p+P_{n-1}*(1-p)$

$P_0=1$ because with $0$ trials you always have $0$ successes (an even number).

For the induction step, assume that it holds for $n-1$. Then: \begin{align} P_n &=(1-P_{n-1})*p+P_{n-1}*(1-p)\\ &=(1-\frac{1}{2}(1+(1-2p)^{n-1}))p+\frac{1}{2}(1+(1-2p)^{n-1})(1-p)\\ &=p-\frac{1}{2}p-\frac{1}{2}p(1-2p)^{n-1}+\frac{1}{2}(1-p)+\frac{1}{2}(1-p)(1-2p)^{n-1}\\ &=p-p+\frac{1}{2}+\frac{1}{2}(1-2p)(1-2p)^{n-1}\\ &=\frac{1}{2}(1+(1-2p)^n). \end{align} So we have shown that it holds for $n$ if we assume it holds for $n-1$. (Completing the proof)