<s>[INST] 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$.
 [/INST] 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} $$
</s>