Solve the recursion $p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$ 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$
 A: $$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$.
A: 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.
