recurrent events-Probability of even number of successes Let E be the event of an even number of successes.
$u_n$:Probability of E occurring at the nth trial not necessarily for the first time
$f_n$:Probability of E occurring at the nth trial for the first time
Let U(x) and F(x) be the corresponding probability generating functions and from that we have the equation $$U(x)=1/(1-F(x))$$
I first wrote a recurrence formula $u_n=p(1-u_{n-1})+qu_{n-1}$
By solving this I got $$U(x)=px/[(1-x)(1-(q-p)x)]$$
Intuitively I feel $F(x)$ should be $p^2x^2/(1-qx)^2$ since this event can be taken as the sum of two geometric random variables. However this is not what I get from the $U(x)$ that I have computed. Did I do something wrong? Any assistance will be very helpful to me. Thanks alot
EDIT: In an answer I saw $u_n$ taken as $[1-(q-p)^{n-1}]p$ which gives results in the $F(x)$ of sum of two random geometric variables but I do not know how this $u_n$ was constructed
 A: Let $u_n$ be the probability that $n$ Bernoulli trials result in an 
even  number of successes.
This occurs if an initial failure is followed by an even number of successes, or an initial success
is followed by an odd number of successes. Therefore $u_0=1$ and for $n\geq 1$
$$u_n=q u_{n-1}+p(1-u_{n-1}).$$
Multiplying by $s^n$ and adding over $n$ we see that the generating function
satisfies
$$U(s)=1+qsU(s)+ps(1-s)^{-1}-psU(s)$$
or
$$2U(s)=[1-s]^{-1}+[1-(q-p)s]^{-1}.$$
Expanding the right hand side using geometric series we find that the coefficients
satisfy $$u_n={1\over 2}+{(q-p)^n\over 2}.$$
Reference: This answer is  taken practically  verbatim from Chapter XI, section 4, page 277 of An introduction to probability theory and its applications (1st edition) by William Feller.
A: Here's a way to do by using a Markov chain:
\begin{align*}
  A &= \begin{pmatrix}
q & p & 0 \\
0 & q & p \\
q & p & 0 
\end{pmatrix}
\end{align*}
Answer will be the third column of the first row in $A^n$, and the generating function for all entries can be obtained directly from the matrix by computing
\begin{align*}
  \left(I-x\, A\right)^{-1}
\end{align*}
Thus, the gf for the required entry is:
\begin{align*}
  G(x) &= -\frac{p^{2} x^{2}}{{\left(p^{2} - q^{2}\right)} x^{2} + 2 \, q x - 1}
\end{align*}
and by partial fractions,
\begin{align*}
  G(x) &= \frac{p^2}{q-p}+\frac{p}{2}\left(\frac{1}{1-x}-\frac{1}{\left(q-p\right)\left(1-(q-p)\, x\right)}\right)
\end{align*}
Hence, the solution for $u_n$ is given by $[x^n]$, which is 
\begin{align*}
  u_n &= \frac{p}{2}\left(1-(q-p)^{n-1}\right)
\end{align*}
Update
We can obtain the recurrence using the markov chain as:
\begin{align*}
  u_n &= p\, v_{n-1} \\
  v_n &= p\, \left(u_{n-1}+w_{n-1}\right)+q\, v_{n-1} \\
  w_n &= q\, \left(u_{n-1}+w_{n-1}\right) \\
  u_1 &= 0 \\
  v_1 &= p \\
  w_1 &= q \\
  u_2 &= p^2 \\
  v_2 &= 2pq \\
  w_2 &= q^2 \\
\end{align*}
$u_n$ is the required answer.
$w_n$ gives the probability of even number of successes, but not exactly at the $n^{th}$ trial.
$v_n$ is for the odd number of successes.
