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.
$\endgroup$ 42 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$
