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.

How to solve this recurrence relation $a_n=(1-p) + (2p-1)a_{n-1}, n \geq 2$ where $a_1= \beta$ and $p$ some arbitrary number.

share|improve this question
3  
Note that $\frac12$ is a fixed point and compute the recursion $b_n=a_n-\frac12$ solves. –  Did Aug 28 '13 at 14:28
add comment

2 Answers

Note that $a_{n+1} = (1-p) + (2p-1)a_n$. Taking the difference with $a_n = (1-p)+(2p-1)a_{n-1}$ we have $a_{n+1} - a_n = (2p-1)(a_n-a_{n-1})$ which gives the second order linear recurrence relation $a_{n+1} = 2pa_n + (2p-1)a_{n-1}$. From here, you can use the method outlined on Wikipedia.

Added later: Easier still, solve it directly. First consider the homoegeneous recurrence relation $a_n^* = (2p-1)a_{n-1}^*$, this has solution $a_n = B(2p-1)^{n-1}$, for some unknown constant $B$. Now we need to find the particular solution, denote it by $a_n'$, for the non-homegenous part. As $1 - p$ is a constant, we try $a_n' = k$, a constant. Substituting that in we find that $k = (1-p) + (2p-1)k$, which has solution $k = \frac{1}{2}$. Then the final solution is $a_n = a_n^* + a_n' = B(2p-1)^{n-1} + \frac{1}{2}$. Now we apply the initial condition $a_1 = \beta$ to find the constant $B$.

share|improve this answer
    
Why would you want to turn a 1st-order recurrence into a 2nd order recurrence? Isn't it easier to solve the 1st order recurrence directly? –  Gerry Myerson Aug 28 '13 at 14:31
1  
The first order recurrence is non-homogeneous, but the second order recurrence is homogeneous. –  Michael Albanese Aug 28 '13 at 14:32
    
Yes --- your point being? –  Gerry Myerson Aug 28 '13 at 14:33
    
You're right, I could have just solved it directly by solving the homegenous recurrence relation first. –  Michael Albanese Aug 28 '13 at 14:35
    
Your solution gives $a_1=\beta + \frac 12$ - and $2p-1$ has become $2p+1$ at one stage. –  Mark Bennet Aug 28 '13 at 17:29
add comment

Take care to consider all the cases.

Note that the general solution of a linear recurrence like $a_n-ka_{n-1}=f(n)$ is the sum of a specific solution $A_n$ of the original recurrence plus an arbitrary solution of the related homogeneous equation $b_n-kb_{n-1}=0$.

The homogeneous equation has solution $b_n=b_0k^n$

In the current case we have $k=(2p-1)$, so we have $B(2p-1)^n$ as the solution to the homogeneous part.

We have $f(n)=1-p$, and if we try a constant solution for $a_n=a$ we find that $$a=(1-p)+(2p-1)a$$ so that $(*)$ $$a=\frac{1-p}{2-2p}=\frac12$$ whence our general solution is $$a_n=\frac 12+B(2p-1)^n$$

We now set $a_1=\beta$ so that $$\beta=\frac12+B(2p-1)$$ and [noting that there is a solution for $p=\frac 12$ only if $\beta=\frac 12$] $$B=\frac 12\cdot\frac{2\beta-1}{2p-1}$$ so that $$a_n=\frac 12+\frac12\cdot (2\beta-1)(2p-1)^{n-1}$$

Note, however, that if $p=1$ we engaged in an illegal division by $0$ at $(*)$, so we have to modify our method. The recurrence becomes $$a_n=a_{n-1}$$ and any constant sequence will do. The inhomogeneous term disappears. The solution for initial condition $a_1=\beta$ is $a_n=\beta$

share|improve this answer
1  
... which, fortunately, is also what we get from the solution when $p=1$, so the answer is correct no matter what $p$ is. –  Rick Decker Aug 28 '13 at 17:36
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.