Solving recurrence $X_n = 4X_{n-1}+5$

Question

$X_n=4X_{n-1}+5$

How come the solution of this recurrence is this?

$X_n=\frac834^n+\frac53$

I also have that $X_0=1$.

I am using telescoping method and I am trying to solve it like this:

$X_n= 5 + 4X_{n-1}$

$X_n= 5 + 4(5+4X_{n-2})$

$X_n= 5 + 4\times5 + 4\times4\times X_{n-2}$

But this leads to me getting $5\times4^{n-1}\times4^n$.

Can some please explain this to me?

Answer 1

If you calculate the first few terms explicitly, you will find that the $n$th term is the sum of an exponential and a geometric series. For example,

$$ X_3 = 4^3 + 5(4^2+4+1). $$ So in general, $$ X_n = 4^n + 5\sum_{k=0}^{n-1}4^k = 4^n +5\frac{1-4^n}{1-4}, $$

which should simplify to the answer you gave.

Answer 2

This is a difference equation and it can be solved using Z-Transform. Take Z-transform of both sides of the equation and then use the initial condition. Ultimately, you will get Z-transform of X and then take its inverse z-transform to get the solution.

Answer 3

Let $x_m=y_m+a\implies y_0=x_0-a=1-a$

$$5=x_n-4x_{n-1}=y_n+a-4(y_{m-1}+a)=y_n-4y_{n-1}-3a$$

Set $-3a=5\iff a=?$ so that $y_n=4y_{n-1}=\cdots=4^ry_{n-r},0\le r\le n$

$r=n\implies y_n=4^ny_0=4^n(1-a)$