3

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) $$

Young
  • 5,492
  • The numerators follow http://oeis.org/A046717 and the denominators follow http://oeis.org/A015518. – lhf Jun 26 '13 at 12:08

3 Answers3

8

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.

eccstartup
  • 1,126
  • Don't worry too much about downvotes: some people just can't stand downvoting instead of showing some tolerance even towards wrong answers. We even have serial downvoters, and many don't even bother to explain their reasons...For example, also my answer here has been downvoted. :) – DonAntonio Jun 26 '13 at 12:10
  • This takes you nowhere closer to solving the recurrence. – OR. Jun 26 '13 at 12:10
  • @Franklin.vp OK, I will write till the end of the solution. – eccstartup Jun 26 '13 at 12:12
  • I learnt it 8 years ago. And I still remember it clearly. – eccstartup Jun 26 '13 at 12:25
  • 1
    Now it is good. There is no reason to get mad at a downvote. I downvoted first when your answer only transformed the rational linear recurrence into another rational linear recurrence. Downvotes and upvotes help organize the answers. I downvoted DonAntonio's answer for the same reason. It is changing it into a branched recurrence, i.e. not helping much to solve it or maybe making it worst. – OR. Jun 26 '13 at 12:31
  • 1
    Thanks @Franklin.vp But can I downvote for your first idea is incomplete? – eccstartup Jun 26 '13 at 12:35
  • If you want. It is your right. Yes, my first idea also works. But is longer. You get first a linear system. The linear system can also be solved by standard methods (essentially reducing it to independent linear recurrences by diagonalizing). – OR. Jun 26 '13 at 12:38
  • let us continue this discussion in chat – eccstartup Jun 26 '13 at 12:39
  • +1 This is nice...and it was also nice before . Some seem to believe that one has to give away the whole, complete answer or else they'll downvote. Don't mind the downvotes, @eccstartup: they won't really affect neither your reputation nor the way most people consider you. – DonAntonio Jun 26 '13 at 13:04
5

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$$

OR.
  • 5,941
  • 2
    Do these formulas give reduced fractions? – lhf Jun 26 '13 at 12:04
  • @lhf In this case, they do, since you always have $p_n \equiv q_n \equiv (-1)^{n-1} \pmod 3$ and $(p_{n+1},,q_{n+1}) = (3q_n,, p_n + q_n) = (q_n,, p_n + q_n) = (q_n,, p_n) = (1)$ inductively. – Daniel Fischer Jun 26 '13 at 12:15
-1

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}$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287