Give a recursion A biased coin is tossed repeatedly. The probability that a toss of the coin results in heads is $p$ with $0 < p < 1$. Give a recursion for the probability that the total number of heads after $n$ tosses is even.
I know that for $n-1$:

*

*if the number of heads is even, the number of tails is odd;


*if the number of heads is odd, the number of tails is even.
So the probability that the number of heads is even is strictly decided by the last trial: $\mathbb{P}(Z_n)=\frac{1}{2}$.
I also know that for $A_n=[$# heads on $n$ trials is even$]$ and $B_n=[$# heads on $n$ trials is odd$]$ we have:
$\mathbb{P}(A_n)=\mathbb{P}(A_{n-1})\mathbb{P}(A_n|A_{n-1})+\mathbb{P}(B_{n-1})\mathbb{P}(A_n|T_{n-1})=\mathbb{P}(A_{n-1})q+[1-\mathbb{P}(A_{n-1})]p$
$=\mathbb{P}(A_{n-1})q+p-\mathbb{P}(A_{n-1})p=p+\mathbb{P}(A_{n-1})(q-p)=p+(q-p)[\mathbb{P}(A_{n-2})\mathbb{P}(A_{n-1}|A_{n-2})+\mathbb{P}(A_{n-2})\mathbb{P}(A_{n-1}|A_{n-2}))]$
$=p+(q-p)(\mathbb{P}(A_{n-2})q+[1-\mathbb{P}(A_{n-2})]p)=p+(q-p)(\mathbb{P}(A_{n-2})q+p-\mathbb{P}(A_{n-2})p)$
$=p+(q-p)(p+\mathbb{P}(A_{n-2})(q-p))=p+p(q-p)+\mathbb{P}(A_{n-2})(q-p)^2=p+p(1-2p)+\mathbb{P}(A_{n-2})(1-2p)^2$
$=p+p-2p^2+\mathbb{P}(A_{n-2})(1-2p)^2=2p-2p^2+\mathbb{P}(A_{n-2})(1-2p)^2$
where, as $n$ decreases to $x$, we have $\mathbb{P}(A_{n-x})(1-2p)^x$ and $2p-2p^2-...-2p^x=\sum_{i=0}^{x}2p^x$ (that for $p\in [0,1]$ converges to $\frac{1}{1-2p}$). Thus I thought to write:
$\mathbb{P}(A_{n-x})(1-2p)^x-\sum_{i=0}^{x}2p^x=\mathbb{P}(Z)\Rightarrow \mathbb{P}(A_{n-x})=\frac{(\frac{1}{2}+\frac{1}{1-2p})}{(1-2p)^x}$ that is different comparing to the solution $\frac{1}{2}+\frac{1}{2}(1-2p)^x$.
Where am I wrong?
Thanks for any help.
EDIT: The second question is Give a recursion for the probability that a sequence of n tosses does not show five or more consecutive heads.
Is it possible to obtain the same result writing
$\mathbb{P}(X\geq 5)=1-\mathbb{P}(X<5)=1-[\binom{n}{0}q^n+\binom{n}{1}pq^{n-1}+\binom{n}{2}p^2q^{n-2}+\binom{n}{3}p^3q^{n-3}+\binom{n}{4}p^4q^{n-4}]$?
 A: Actually, your recursion starts fairly good:
$$\mathbb{P}(A_n) = \mathbb{P}(A_{n-1)})q + [1 - \mathbb{P}(A_{n-1})]p$$
which can be rewritten, with $p_n = \mathbb{P}(A_n)$, as
$$p_n = (1-p)p_{n-1}+p(1-p_{n-1}) = (1-2p)p_{n-1}+p$$
That gives a recursion formula of the form $p_{n+1} = ap_n +b$, with $p_0=1$. There is a standard method to solve this kind of formula, that is :

*

*Find the fixed point : $l=al+b$. Here, $ l =(1-2p)l+p$, which gives $l=1/2$.

*Defines a new sequence $v_n = p_n -l$. $v_n$ is a geometric sequence. Indeed:
$$v_{n+1}=p_{n+1}-l = ap_n+b - (al+b) = a(p_n-l) = av_n$$

*Therefore, $v_n = a^{n}v_0 = a^{n}(p_0-l)$

*Finally, $p_n = v_n+l = a^{n}(p_0-l)+l$
This gives in your case
$$p_n = (1-2p)^{n}(1-1/2)+1/2 = \frac{1}{2}+\frac{1}{2}(1-2p)^n$$
That should answer the first question!
A: Let $a_n$ be the probability that, after $n$ tosses, the number of heads is even.
$$
\begin{align}
a_n
&=p(1-a_{n-1})+(1-p)a_{n-1}\tag1\\[9pt]
&=p+(1-2p)a_{n-1}\tag2\\[3pt]
a_n-\frac12
&=(1-2p)\left(a_{n-1}-\frac12\right)\tag3\\
&=(1-2p)^n\left(a_0-\frac12\right)\tag4\\
a_n
&=\frac12+\frac12(1-2p)^n\tag5
\end{align}
$$
Explanation:
$(1)$: the probability that on this toss we have an even number of heads
$\phantom{\text{(1):}}$ is the probability that last toss we had an odd number of heads
$\phantom{\text{(1):}}$ and then rolled a head, plus the probability that last toss we had
$\phantom{\text{(1):}}$ an even number of heads and then rolled a tail
$(2)$: simplify
$(3)$: rewrite $(2)$ with $a_n+x=(1-2p)(a_{n-1}+x)$; $x=-\frac12$
$(4)$: induction
$(5)$: solve with $a_0=1$ ($0$ is an even number of heads)
So your answer looks correct.
