How do you go about solving difference equations? Say you have something of the form
$p_1 = p$
$p_n=kp_{n-1}+(1-k)(1-p_{n-1})$
How does one go about finding $p_{n}$ in terms of $n,p$ and $k$?
In my notes here's how it's found
$p_n-1/2 = (2k-1)(p_{n-1}-1/2)=(2k-1)^{n-1}(p_1-1/2)$
But to be honest I don't understand how you'd arrive at the conclusion that you want to factorize the RHS like they did. In a different problem it was actually given that 
$p_n$ is of the form $A+B{\lambda}^n$.
 A: If you reorganise your equation, you get:
$$p_n=(2k-1)p_{n-1}+(1-k)$$
One way of solving this is to solve the homogeneous equation $$p_n=(2k-1)p_{n-1}$$ to obtain $\lambda=(2k-1)$ in your standard solution, and then look for a particular solution with $p_n=constant$ to give a general solution in the form you have suggested - the particular solution can be added to any multiple of the general solution of the homogeneous equation (linearity).
An alternative way is to turn the whole equation into a homogeneous equation by setting $p_n = q_n+a$. This gives:
$$q_n+a=(2k-1)(q_{n-1}+a)+(1-k)$$ or:
$$q_n=(2k-1)q_{n-1}+(2k-1)a+(1-k)-a =(2k-1)q_{n-1}+(k-1)(2a-1)$$
And if we set $a=\frac 1 2$ we get the simplified equation:
$$q_n=(2k-1)q_{n-1}$$
Giving $$q_n=(2k-1)^{n-1}q_1$$
And we get the solution for $p_n$ by substituting back.
They are just two approaches to solve the same equation - sometimes one is more convenient than the other.
A: You are given
$$\mathrm {p_1 = p}$$
$$\mathrm { p_n=k \cdot p_{n-1}+(1- k)(1-p_{n-1})}$$
Write the latter in the form
$$\eqalign{ 
  & \mathrm {{p_n} = k{p_{n - 1}} + (1 - k)(1 - {p_{n - 1}})}  \cr 
  & \mathrm {{p_n} = k{p_{n - 1}} + 1 + k{p_{n - 1}} - k - {p_{n - 1}}}  \cr 
  & \mathrm {{p_n} = \left( {2k - 1} \right){p_{n - 1}} - (k - 1) }\cr} $$
Now subtract $1/2$ from the equation and rearrange
$$\eqalign{
  & \mathrm {{p_n} = \left( {2k - 1} \right){p_{n - 1}} - \left( {k - 1} \right)}  \cr 
  &\mathrm { {p_n} - \frac{1}{2} = \left( {2k - 1} \right){p_{n - 1}} - \left( {k - 1} \right) - \frac{1}{2} } \cr 
  & \mathrm {{p_n} - \frac{1}{2} = 2\left( {k - \frac{1}{2}} \right){p_{n - 1}} - \left( {k - \frac{1}{2}} \right) } \cr 
  & \mathrm {{p_n} - \frac{1}{2} = \left( {2{p_{n - 1}} - 1} \right)\left( {k - \frac{1}{2}} \right)  }\cr 
  & \mathrm {{p_n} - \frac{1}{2} = \left( {{p_{n - 1}} - \frac{1}{2}} \right)\left( {2k - 1} \right) }\cr} $$
Define now
$$\mathrm {{p_n} - \frac{1}{2} = {u_n}}$$
Then you have that, with $2 \mathrm k-1=\lambda$
$${\mathrm p_{\mathrm n}} - \frac{1}{2} = \left( {{ \mathrm p_{\mathrm n - 1}} - \frac{1}{2}} \right)\left( {2 \mathrm k - 1} \right)$$
$${\mathrm u_n} = \lambda {\mathrm u_{\mathrm n - 1}}$$
We get by induction on $\mathrm n$ that
$${\mathrm u_{\mathrm n} = \mathrm \lambda ^{\mathrm n - 1} \mathrm u_1}$$
Or that
$$\eqalign{
  & \mathrm  {u_n} = {\lambda ^{\mathrm n - 1}}\mathrm {u_1}  \cr 
  & \mathrm {p_n} - \frac{1}{2} = {\left( {2 \mathrm k - 1} \right)^{\mathrm n - 1}}\left( \mathrm {p - \frac{1}{2}} \right)  \cr 
  & \mathrm {p_n} = {\left( {2 \mathrm  k - 1} \right)^{\mathrm n - 1}}\left( \mathrm {p - \frac{1}{2}} \right) + \frac{1}{2} \cr} $$
A: Here's another approach. To keep the notation simple, let $a=2k-1$ and $b=1-k$, so that your recurrence is $p_n=ap_{n-1}+b$. Using the recurrence repeatedly, we 'unwind' it:
$$\begin{align*}
p_n&=ap_{n-1}+b\\
&=a(ap_{n-2}+b)+b\\
&=a^2p_{n-2}+ab+b\\
&=a^2(ap_{n-3}+b)+ab+b\\
&=a^3p_{n-3}+a^2b+ab+b\;.
\end{align*}$$
At this point it's not hard to see that after $k$ applications of the recurrence we'll have
$$p_n=a^kp_{n-k}+a^{k-1}b+a^{k-2}b+\ldots+ab+b=a^kp_{n-k}+b\sum_{i=0}^{k-1}a^i\;.\tag{1}$$
If you set $k=n-1$, this becomes 
$$\begin{align*}
p_n&=a^{n-1}p_1+b\sum_{i=0}^{n-2}a^i\\
&=a^{n-1}p+b\left(\frac{1-a^{n-1}}{1-a}\right)\\
&=p(2k-1)^{n-1}+(1-k)\left(\frac{1-(2k-1)^{n-1}}{1-(2k-1)}\right)\\
&=p(2k-1)^{n-1}+(1-k)\left(\frac{1-(2k-1)^{n-1}}{2(1-k)}\right)\\
&=\left(p-\frac12\right)(2k-1)^{n-1}+\frac12\;.
\end{align*}$$
Properly speaking you should then prove this by induction on $n$, since $(1)$ wasn't rigorously verified.
