Find a formula for the sequence $(a_n)$ I would appreciate if somebody could help me with the following problem
Q : Find $a_n=?$
$$a_1=1, a_{n+1}=\frac{a_n+4}{a_n+1}(n=1,2,3,\cdots) $$
 A: HINT：
Step 1:
Solve:$$x=\frac{x+4}{x+1}$$ first.
You get $x=2$,and $x=-2$.
Step 2:
Divide
$$a_{n+1}+2=\frac{a_n+4}{a_n+1}+2,$$
and
$$a_{n+1}-2=\frac{a_n+4}{a_n+1}-2.$$
You get $$\frac{a_{n+1}+2}{a_{n+1}-2}=(-3)\frac{a_{n}+2}{a_{n}-2}.$$
Step 3:
Set $b_n=\frac{a_{n}+2}{a_{n}-2}$,so $b_1=-3.$
You get $$b_n=(-3)^n.$$
Step 4:
Solve $\frac{a_{n}+2}{a_{n}-2}=(-3)^n.$
You get $$a_n=2\cdot{} \frac{(-3)^n+1}{(-3)^n-1}$$
PS:I don't know why people just voted down.
A: Idea: Try to make it linear.
First idea (longer):
Write $$a_n:=p_n/q_n.$$ Then you get 
$$\frac{p_{n+1}}{q_{n+1}}=\frac{p_n+4q_n}{p_n+q_n}$$
i.e. you get a linear recurrence for the two sequences $p_n$ and $q_n$. 
$$
\begin{align*}
p_{n+1}&:=p_n+4q_n\\
q_{n+1}&:=p_n+q_n
\end{align*}
$$
Now, there are (many) methods for solving linear recurrences. First you can change variables to diagonalize the matrix of coefficients on the right (or at least make it triangular). Then you can solve the system easily. Keywords that could points you to different methods for solving linear recurrences are: generating series, Z-transform, ... 
If you have doubts ask more, but give it a try first and also read a little, for example here (http://en.wikipedia.org/wiki/Recurrence_relation#Solving).
Second idea (shorter):
OH! Wikipedia has an article about this type of recurrences too. Here (http://en.wikipedia.org/wiki/Rational_difference_equation)
They have a substitution there that will gives you a linear recurrence in one variable directly, instead of a system first like what I did. That is faster.
So, write $a_n=x_{n+1}/x_n-1$, in your case. We get 
$$
\frac{x_{n+2}}{x_{n+1}}-1=\frac{x_{n+1}/x_n+3}{x_{n+1}/x_n}
$$
This yields
$$
x_{n+2}+x_{n+1}=x_{n+1}+3x_n
$$
This is homogeneous, and linear in one variable. So you can solve easily.
So, in general if the recurrence is 
$$z_{n+1}=\frac{az_n+b}{cz_n+d}$$
put $$z_n:=x_{n+1}/x_n-d/c$$
and you get 
$$x_{n+2}-\alpha x_{n+1}+\beta x_{n=0}$$
where 
$$\alpha:=(a+d)/c$$
and
$$\beta:=(ad-bc)/c^2$$
A: An idea:
$$a_{n+1}=\frac{p_{n+1}}{q_{n+1}}\;,\;\;\text{with}\;\;q_{n+1}=p_n+q_n\;,\;\;p_{n+1}=\begin{cases}2q_{n+1}+1&,\;\;\;n\;\;\text{is odd}\\{}\\2q_{n+1}-1&,\;\;\;n\;\;\text{is even}\end{cases}$$
