Solving this recursive relation

Question

I want to solve this recursive relation:

$$i_{n+1}=4i_{n}+9$$ where the $i_1=t$ that $t \in \mathbb{N}$

I tried to make like relation about Tower of Hanoi, but no good thing happened.

How can I do this?

Answer 1

We have $$i_{n+1}+3 = 4(i_n+3)$$Defining $t_n = i_n+3$, we obtain $$t_{n+1} = 4t_n \implies t_n = 4^{n-1} t_1 \implies i_n = 4^{n-1}(i_1+3)-3$$

Answer 2

$$a_{n+1}=4a_n+9$$ $$4a_n=16a_{n-1}+36$$ $$\vdots$$ $$4^{n-2}a_3=4^{n-1}a_2+4^{n-2}.9$$ $$4^{n-1}a_2=4^na_1+4^{n-1}9$$ Adding all the equations, you get $a_{n+1}=4^na_1+9(1+4+\dots+4^{n-1})$. $$a_{n+1}=4^na_1+9\frac{4^n-1}{3}$$ $$a_n=4^{n-1}(a_1+3)-3$$

Answer 3

Like all linear recurrence relations, you first solvethe homogeneous equation: $$ \begin{cases} u_{n+1}=4u_n\\u_1=t\end{cases}$$ which is a geometric sequence.

Then you try to find one particular solution of the complete equation: $u_{n+1}=4u_n + 9$. This should be a constant, which you can calculate, setting $ u_n=C$.