Answer to Question #197186 in Discrete Mathematics for sakibur rahman

Question

Find the solution of the recurrence relation: xn=3xn-1 + 1, where,  x0=4

Answer 1

Let us find the solution of the recurrence relation: $x_n=3x_{n-1} + 1$, where $x_0=4.$

For this firstly, let us solve the characteristic equation of the homogeneous equation $x_n-3x_{n-1}=0$ :

$k-3=0$ or $k=3.$ It follows that the particular solution of the equation is $x_n=a=const$, where $a=3a+1,$ and hence $a=-\frac{1}{2}.$ The solution of the recurrence relation: $x_n=3x_{n-1} + 1$

is $x_n=C\cdot3^n-\frac{1}{2}.$ Taking into account that $x_0=4,$ we conclude that $4=x_0=C-\frac{1}{2}$, and thus $C=\frac{9}{2}.$ Consequently,

$x_n=\frac{9}{2}\cdot3^n-\frac{1}{2}=\frac{3^{n+2}-1}{2}.$