Solve the recursion $p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$

Question

Solve the recursion $p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$

$p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$

$= p + (1-2p)p_{n-1}$ I can see that this step simply rearranges the expression, but what's the point of it? What are we trying to accomplish here? Is it to combine the $p_{n-1}$ terms?

$p_n - \frac{1}{2} = (1-2p)(p_{n-1} - \frac{1}{2})$ Again, I'm not quite sure why the solutions rearranged the expression this way

$p_n = \frac{1}{2} + C(1-2p)^n$ Here I assume $C = (p_{n-1} - \frac{1}{2})$?

And as $p_0 = 1$, $C = \frac{1}{2}$, and

$p_n = \frac{1}{2} + \frac{1}{2}(1- 2p)^n$

Answer 1

$$p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}= p + (1-2p)p_{n-1}$$ I can see that this step simply rearranges the expression, but what's the point of it? What are we trying to accomplish here? Is it to combine the $p_{n-1}$ terms?

Yes.

$$p_n - \frac{1}{2} = (1-2p)\left(p_{n-1} - \frac{1}{2}\right)$$ Again, I'm not quite sure why the solutions rearranged the expression this way.

This looks like a cooked-up example. It appears that, instead of solving for $p_n$, the person who wrote the solution is looking for a a relation that $\displaystyle q_n=p_n-{1\over2}$ satisfies. That would turn the equation into $$q_n = (1-2p) q_{n-1}.$$ The solution to this will be simply $q_n = (1-2p)^n \cdot C$, for some constant $C$ (which also equals $q_0$): $$\eqalign{ q_1 &= (1-2p) q_0\cr q_2 &= (1-2p) q_1 = (1-2p)^2 q_0\cr q_3 &= (1-2p) q_2 = (1-2p)^3 q_0\cr }$$

And as $p_0 = 1$, $\displaystyle q_0=1-{1\over2}$, $\displaystyle C = q_0=\frac{1}{2}$, $$q_n = {1\over2}(1-2p)^n$$ so $\displaystyle p_n = {1\over2} + q_n = {1\over2}+{1\over2}(1-2p)^n$.

Answer 2

It's a 2-state Markov chain where with probability $p$ one switches to the other state and with probability $q=(1-p)$ stays in the same place. The binomial expansion of $(pX + qY)^n$ gives the distribution of the number of switch (X) and stay (Y) steps. Therefore the sum of the probabilities of even/odd number of X's is $\frac{(p+q)^n \pm (-p + q)^n}{2} = \frac {1 \pm (1-2p)^n}{2}$. This tells the probabilities of ending in the initial state or in its opposite state.