Markov chain transient on one side There are $n$ yellow balls and $n+2$ purple balls in a bag. When a yellow ball is drawn it is discarded and a purple ball is also discarded; when a purple ball is drawn, it is placed back in and two balls (one yellow, one purple) are added. I need to show the probability $P_n$ that it terminates (yellow ball count reaches $0$) is $1/(n+1)$. I've made a few Markov chains to try and do proof by induction but I can't even prove for the case $n=1$, only $n=0$.

I've drawn a Markov chain with a few steps up and down from $P_n$ (denominator gaining $2$ as purple gets drawn, losing $2$ when yellow does). I've also shown $P_0=1$ by drawing another chain around yellow near termination.

My formula for $P_n$ is
$$
P_n
=
\Bigl(\frac{n}{2n+2}\Bigr)P_{n-1}
+
\Bigl(\frac{n+2}{2n+2}\Bigr)P_{n+1}
$$
where $n$ is the number of yellows at that stage in the chain

But I don't know how to prove it for $n > 0$ as any such $P_n$ also has a $P_{n+1}$ value that I can't calculate. 
 A: Let $y$ represent the varying number of yellow balls in the bag.

For each nonnegative integer $n$, let $P_n$ be the probability that, from a starting state of $y=n$, the state $y=0$ is eventually reached.

Claim:$\;P_n={\large{\frac{1}{n+1}}}$, for all $n$.

Proof:

For each pair of integers $m,n$ with $m > 0$ and $0\le n\le m$, let $X_m(n)$ be the event that, from a starting state of $y=n$, the state $y=0$ is reached without first reaching the state $y=m$.

Let $p_m(n)=P\bigl(X_m(n)\bigr)$.

Lemma:$\;$For all $m,n$ we have
$$
p_m(n)
=
\frac{2na-(n-1)}{n+1}
$$
where $a=p_m(1)$.

Proof of the lemma:

Fixing a positive integer $m$, proceed by induction on $n$, for $0\le n\le m$.

We need the base cases $n=0$ and $n=1$.

For the case $n=0$ we have $p_m(0)=1$, and identically. for $n=0$ we have
$$
\frac{2na-(n-1)}{n+1}=1
$$
so the case $n=0$ is verified.

For the case $n=1$ we have $p_m(1)=a$, and identically. for $n=1$ we have
$$
\frac{2na-(n-1)}{n+1}=a
$$
so the case $n=1$ is verified.

If $m=1$ we are done (since $n$ is restricted to $0\le n\le m$), so assume $m > 1$.

Next assume that, for some positive integer $n < m$, we have
$$
\left\{
\begin{align*}
p_m(n-1)&=
\frac{2(n-1)a-(n-2)}{n}
\\[4pt]
p_m(n)&=
\frac{2na-(n-1)}{n+1}
\\[4pt]
\end{align*}
\right.
$$
Then we get
\begin{align*}
&
p_m(n)
=
\Bigl(\frac{n}{2n+2}\Bigr)p_m(n-1)
+
\Bigl(\frac{n+2}{2n+2}\Bigr)p_m(n+1)
\\[4pt]
\implies\;&
p_m(n+1)
=
\Bigl(\frac{2n+2}{n+2}\Bigr)
\left(
p_m(n)
-
\Bigl(\frac{n}{2n+2}\Bigr)p_m(n-1)
\right)
\\[4pt]
\end{align*}
Substituting for $p_m(n)$ and $p_m(n-1)$, and then simplifying, we get
$$
p_m(n+1)
=
\frac{2(n+1)a-n}{n+2}
$$
which completes the induction.

This completes the proof of the lemma.

Applying the lemma to the boundary condition $p_m(m)=0$ yields
$$
\frac{2ma-(m-1)}{m+1}=0
$$
hence $a={\large{\frac{m-1}{2m}}}$.

Thus we have $p_m(1)={\large{\frac{m-1}{2m}}}$, for all $m$.

Returning to the main claim, proceed by induction on $n$.

We need the base cases $n=0$ and $n=1$.

It's immediate that $P_0=1$, so the claim holds for the case $n=0$.

For the case $n=1$ we can argue as follows . . .

Noting that
$$
X_2(1)\subset X_3(1)\subset X_4(1)\subset\cdots
$$
it follows that
$$
P\left(\bigcup_{m=2}^\infty X_m(1)\right)
=
\lim_{m\to\infty}P\bigl(X_m(1)\bigr)
$$
and then, noting that
$$
P_1
=
P\left(\bigcup_{m=2}^\infty X_m(1)\right)
$$
we get
$$
P_1
=
\lim_{m\to\infty}P\bigl(X_m(1)\bigr)
=
\lim_{m\to\infty}p_m(1)
=
\lim_{m\to\infty}\frac{m-1}{2m}
=
\frac{1}{2}
$$
so the claim holds for the case $n=1$.

Next assume that, for some positive integer $n$, we have $P_{n-1}={\large{\frac{1}{n}}}$ and $P_n={\large{\frac{1}{n+1}}}$.

Then we get
\begin{align*}
&
P_n
=
\Bigl(\frac{n}{2n+2}\Bigr)P_{n-1}
+
\Bigl(\frac{n+2}{2n+2}\Bigr)P_{n+1}
\\[4pt]
\implies\;&
P_{n+1}
=
\Bigl(\frac{2n+2}{n+2}\Bigr)
\left(
P_n
-
\Bigl(\frac{n}{2n+2}\Bigr)P_{n-1}
\right)
\\[4pt]
\end{align*}
Substituting for $P_n$ and $P_{n-1}$, and then simplifying, we get
$$
P_{n+1}
=
\frac{1}{n+2}
$$
which completes the induction.

This completes the proof.
