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.
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.