# A basic problem on recurrence relation

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.

-
Note that $\frac12$ is a fixed point and compute the recursion $b_n=a_n-\frac12$ solves. – Did Aug 28 '13 at 14:28

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

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

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$

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