# How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$.

I know that the characteristic equation is $r-2 = 0$ which has the root $r = 2$. Usually I find constants $A$ and $B$ by $a_n=Ar^n+Br^n$. It looks like I cannot apply this here because $a_n=An+B$ is given. The solution is $A = -1$ and $B = -7$. I don't know how to get this answer. Can anyone help me please.

• I think the relationship is $a_n=A\cdot n+B$ – lab bhattacharjee Oct 31 '13 at 18:04
• If so, $$A\cdot n+B=2\{A(n-1)+B\}+n+5$$ $$\implies A\cdot n+B=n(2A-1)+B+5-2A$$ Now compare the coefficients of $n$ and the constants – lab bhattacharjee Oct 31 '13 at 18:16
• how you get n(2a-1)+B+5-2A shouldn't it be like 2A(n-1)+2B+n+5 – pengyal Oct 31 '13 at 18:39
• try to group terms containing $n$ and the terms not containing $n$ separately – lab bhattacharjee Nov 1 '13 at 3:54

## 2 Answers

Consider the homogeneous recurrence relation $a_n=2a_{n-1}$ where $n\geq1$. The characteristic equation is $x-2=0$, where $x=2$ is the root of the characteristic root. Thus the general solution is $a_n=a2^n$ where $a$ is a constant. Let $a_n=bn+c$ where $b$ and $c$ are constants. We do this because $b_n=n+5$, so a linear equation is a proper guess. Substituting this into our original recurrence relation we see that $bn+c=2(b(n-1)+c)+(n-1)+5$ implies that $bn+c=(2b+1)n+(-2b+2c+5)$. Equating the coefficients of these polynomials we see that $b=-1$ and $c=-7$. Thus the particular solution is $a_n=-n-7$. Combining the general solution and the particular solution we have $a_n=a2^n-n-7$.

You have $\forall n ~:~ a_n = 2~a_{n-1} + n + 5$ and $\forall n ~:~ a_n = A~n+B$. So construct the equations

$$\begin{array} {c|cc} n & a_n = 2~a_{n-1} + n + 5 & a_n = A~n+B \\ \hline 1 & a_1 = 2~a_{0} + 6 & a_1 = A+B \\ 2 & a_2 = 2~a_{1} + 7 & a_2 = 2~A+B \\ 3 & a_3 = 2~a_{2} + 8 & a_3 = 3~A+B \\ \end{array}$$

Simple system of 6 linear equations, 6 variables. Solve for $A$ and $B$.

Or you can be a bit more indirect: Plug $\forall n ~:~ a_n = A~n+B$ into $\forall n ~:~ a_n = 2~a_{n-1} + n + 5$

$$\forall n ~:~ A~n + B = 2~A~(n-1) + 2~B + n + 5$$

Plug $n=0$ in to get

$$B = 2~B - 2A + 5$$

Plug $n=1$ in to get

$$A+B = 2B + 1 + 5$$

So 2 equations, 2 variables.