How do I solve the recurrence relation $A_n=2A_{n-1}+3 | A_0=1$

Question

I tried working it backwards and ended up with $2+3n$, which is incorrect, and when I work it forwards I et nowhere other than I found that each time in is increased, $A_n$ is increased by $2^{n+1}$. I am not sure how to solve it from there. Help would be appreciated! Thanks.

EDIT: $A_0$ = 1, I'm sorry I typed the wrong number.

Answer 1

hint :"We have not yet learned induction in my discrete mathematics class, and I am not allowed to use it yet. " so you can do this : $$A_{n+1}=2A_{n}+3\\A_{n+1}=2(2A_{n-1}+3)+3=2^2A_{n-1}+6+3\\ A_{n+1}=2^2(2A_{n-2}+3)+9=2^3A_{n-2}+12+6+3\\ A_{n+1}=2^3(2A_{n-3}+3)+12+9\\=2^4A_{n-3}+24+12+6+3\\...$$so $$A_n=a(2^n)+b$$now plug $$A_0,A_1$$ to find $a,b$ $$n=1 \to A_1=a(2^1)+b=5\\n=2 \to A_2=a(2^2)+b=13$$find $a,b$ $$a=4,b=-3\\A_n=4(2^n)-3$$

Answer 2

Call $B_n=A_n+3$. You have $$\begin{cases}B_{n+1}=2B_n\\ B_0=4\end{cases}$$

Answer 3

There is a general solution to such recurrence relations.

Suppose we have $x_n=ax_{n-1}+b$ with $a\neq0$ and $a_0$ given. If $b=0$ the solution is obvious.
If $b\neq 0$ we can solve immediatly for the constant solution $x_n=x$. This means $x=ax+b$ or $x=b/(1-a)$.
Next let $y_n=x_n-x$. Then $y_n=ay_{n-1}$, which means $y_n=a^ny_0$ (this is the case of $b=0$).
Substituting $x_n$ we find
$x_n=a^n(x_0-x)+x=a^n\left(x_0-b/(1-a)\right)+b/(1-a)$.

So in your example (for $A_0=0$) $A_n=2^n*3-3$
Or $A_n=2^n*4-3$ for $A_0=1$

Answer 4

$$A_n = 2A_{n-1}+3$$ $$\Leftrightarrow A_n -2A_{n-1} = 3$$ $$\Leftrightarrow A_{n+1} -2A_{n} = 3$$ Thus, the characteristic equation of the homogeneous part is $$c(\lambda)=\lambda - 2$$ Since its root is $\lambda^* = 2$, the homogeneous solution is $$A_n = c\cdot 2^n$$ Because $A_0 = 1$ and $A_1 = 5$ we can conclude $ c = 4$: $$A_0 = 4\cdot2^0-3$$ $$A_1 = 4\cdot2^1-3$$

Thus, $$A_n =4\cdot 2^n-3$$