Question

Solve the following recurrence relation
a) an = 3an-1. n≥1
b) an = 5an-1 + 2 n≥1
c) an = 7an-1 + n n≥1

Answer 1

a) $a_n = 3a_{n-1}, n≥1$

The characteristic equation is $\lambda =3$, and therefore the solution is $a_n=C\cdot 3^n$ where $C=a_0.$

b) $a_n = 5a_{n-1} + 2, n≥1$

The characteristic equation of $a_n = 5a_{n-1}$ is $\lambda =5$, and therefore the solution is $a_n=C\cdot 5^n+b_n$ where $b_n = b$ is a solution of $a_n = 5a_{n-1} + 2$. Therefore, $b=5b+2$ which is equivalent to $b=-\frac{1}{2}$ . So, $a_n=C\cdot 5^n-\frac{1}{2}.$ If $n=0$ then $a_0=C-\frac{1}{2}$, and thus $C=a_0+\frac{1}{2}.$ Consequently, the solution is $a_n=(a_0+\frac{1}{2})\cdot 5^n-\frac{1}{2}$.

c) $a_n = 7a_{n-1} + n, n≥1$

The characteristic equation of $a_n = 7a_{n-1}$ is $\lambda =7$, and therefore the solution is $a_n=C\cdot 7^n+b_n$ where $b_n = an+b$ is a solution of $a_n = 7a_{n-1} + n$. Therefore, $an+b=7(a(n-1)+b)+n$ which is equivalent to $(6a+1)n+6b-7a=0$. So, $6a+1=0$ and $6b-7a=0$ which is equivalent to $a=-\frac{1}{6}$ and $b=-\frac{7}{36}.$ Therefore, $a_n=C\cdot 7^n-\frac{1}{6}n-\frac{7}{36}.$ If $n=0$ then $a_0=C-\frac{7}{36}$, and thus $C=a_0+\frac{7}{36}.$ Consequently, the solution is $a_n=(a_0+\frac{7}{36})\cdot 7^n-\frac{1}{6}n-\frac{7}{36}.$