1
$\begingroup$

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

  • 0
    [These notes](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf) might be helpful, especially Section 5.2012-05-12

3 Answers 3

1

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.

3

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.

2

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} $

  • 0
    @J.D. Tryi$n$g a new style. I'm reading an old essay by Truesdell and he uses non italic variables.2012-05-12