Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

3 Answers

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.