trouble with non homogenous recurrence relation

Question

I'm having trouble approaching this problem. The $+3$ at the end is throwing me off because this makes this non homogeneous I believe. Any suggestions?

$$a_n=2a_{n-1}+3$$ for $$n\ge1, a_0 = 1$$

for the characteristic equation $i$ have, $x^2−2x−3$?

Therefore, the roots would be $3$ and $-1$?

Answer 1

Hint:

$1)$ Solve the recurrence $a_n=2a_{n-1}$ like usual. The solution will be called $b_n$. Think about a geometric sequence here.

$2)$ Take a particular solution $p$ of $a_n=2a_{n-1}+3$. Think about some constant.

$3)$ Your general solution will be $a_n=b_n+p$

Answer 2

Try the substitution $b_n=a_n+3$ and find the initial value $b_0$ and recursion formula for this sequence $b_n$. Once you have solved this, you can easily find the formula for $a_n$.

Answer 3

The common trick I use for solving some non-homogenous recurrence relations is to get rid of the non-homogenous part. This can be done by writing:

$$a_n - 2a_{n-1} = 3 = a_{n-1} - 2a_{n-2}$$

Hence we reduce the equation to a homogenous one, namely $a_n - 3a_{n-1} + 2a_{n-2} = 0$. Now you can find the characteristic equation and find the general term.

Answer 4

The most straightforward, elementary approach is to ‘unwind’ the recurrence:

$$\begin{align*} a_n&=2a_{n-1}+3\\ &=2(2a_{n-2}+3)+3\\ &=2^2a_{n-2}+2\cdot3+3\\ &=2^2(2a_{n-3}+3)+2\cdot3+3\\ &=2^3a_{n-3}+2^2\cdot3+2\cdot3+3\\ &\;\;\vdots\\ &=2^ka_{n-k}+3\sum_{i=0}^{k-1}2^i\\ &\;\;\vdots\\ &=2^na_0+3\sum_{i=0}^{n-1}2^i\\ &=2^n+3\left(2^n-1\right)\\ &=2^{n+2}-3\;. \end{align*}$$

The step in the middle is the result of recognizing the pattern, so it isn’t actually rigorous, and the final result should be proved by induction on $n$.

A slicker approach that is applicable whenever the recurrence takes the form $a_n=c_0a_{n-1}+c_1$ is to make a change of variable. Let $b_n=a_n-d$, where $d$ is a constant yet to be determined. Then $a_n=b_n+d$, and the recurrence can be written

$$b_n+d=2(b_{n-1}+d)+3\;,$$

or

$$b_n=2b_{n-1}+d+3\;.$$

Now choose $d$ to make the recurrence homogeneous: let $d=-3$, so that $b_n=2b_{n-1}$. Then it should be clear that $b_n=2^nb_0$, since to get from $b_0$ to $b_n$ we just double the number $n$ times. Now $b_0=a_0-d=1-(-3)=4$, so $b_n=4\cdot2^n=2^{n+2}$. Finally,

$$a_n=b_n+d=2^{n+2}+(-3)=2^{n+2}-3\;.$$

Answer 5

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With $\ds{a_{0} = 1}$:

\begin{align} a_{n} & = 2a_{n - 1} + 3 \implies a_{n} + 3 = 2\pars{a_{n - 1} + 3} \\[5mm] \bbox[#ffc,15px]{\ds{a_{n} + 3}} & = 2\pars{a_{n - 1} + 3} = 2^{2}\pars{a_{n - 2} + 3} = \cdots = 2^{n}\pars{a_{0} + 3} = \bbox[#ffc,15px]{\ds{2^{n} \times 4}} \end{align}

---

$$\bbx{\ds{a_{n} = 2^{n + 2}\ -\ 3}}$$