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

-
This is a linear recurrence with constant coefficients - these have a well studied theory which handles these very powerfully. For example, your recurrence had the form $p_n = ap_{n-1} + C$ so one can immediately deduce $p_n$ is in the form the "different problem" had. –  Ragib Zaman May 12 '12 at 14:52
These notes might be helpful, especially Section 5. –  JeffE May 12 '12 at 15:19

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.

-

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.

-

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}

-
I'm curious, why the \mathrm? –  user2468 May 12 '12 at 15:11
@J.D. Trying a new style. I'm reading an old essay by Truesdell and he uses non italic variables. –  Pedro Tamaroff May 12 '12 at 15:30