How to calculate the general formula $a_n$ for the following sequence: $$a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$$ where $a_1=\frac{1}{2}, a_2=\frac{1}{4}$

  • $\begingroup$ Use the initial values $a_1, a_2$ to calculate $a_3, a_4, a_5, ...$ and look to see if a pattern emerges which allows you to write a new formula for $a_n$. $\endgroup$ – user2307487 Apr 24 '13 at 6:36

$$\begin{align}&a_{n} = \frac{1}{2 a_{n-1}} + 2 a_{n-2}\\ \iff & 2 a_{n} a_{n-1} + 1 = 2 ( 2 a_{n-1} a_{n-2} + 1)\\ \implies & 2 a_{n} a_{n-1} + 1 = 2^{n-2} (2 a_2 a_1 + 1 ) = \frac{5}{16} 2^n\\ \implies & a_{n}/a_{n-2} = \frac{\frac{5}{16} 2^n - 1}{\frac{5}{32} 2^n - 1}\\ \implies & a_{n} = \begin{cases} a_2 \prod_{k=0}^{m-1} (\frac{\frac{5}{16} 2^n - 4^k}{\frac{5}{32} 2^n - 4^k}), & \text{for}\;n = 2m\\ a_1 \prod_{k=0}^{m} (\frac{\frac{5}{16} 2^n - 4^k}{\frac{5}{32} 2^n - 4^k}), & \text{for}\;n = 2m+1 \end{cases} \end{align}$$

This give us a pretty ugly list $a_i = ( \frac{1}{2},\frac{1}{4},3,\frac{2}{3},\frac{27}{4},\frac{38}{27},\frac{1053}{76},\frac{3002}{1053},\frac{167427}{6004},\frac{957638}{167427}, \ldots )$ and I cannot see any obvious pattern in it.

  • $\begingroup$ Thank you very much. This one is easy to obtain. But I think it would be better if there is no $\Pi$ or $\Sigma$ in $a_n$, because it does no help in calculating $a_n$, i.e. it's much easier to calculate $a_n$ from $a_1$ and $a_2$ . But $2^n$ in the general formula is okay, because we can calculate it with some techniques. But anyway, thank you very much for your answer. $\endgroup$ – zijuexiansheng Apr 24 '13 at 7:50
  • 1
    $\begingroup$ @zijuexiansheng: Are you just looking for a fast algorithm to compute or are you looking for a "simple" formula? It is very rare that an arbitrary recurrence will give a general formula which has no $\sum$ or $\prod$ or something complicated... $\endgroup$ – Aryabhata Apr 24 '13 at 8:25
  • $\begingroup$ @Aryabhata: Yes, and I think usually a general formula is sufficient. This recurrence looks neat. That's why I think there might be a general formula for it without $\sum$ or $\prod$ $\endgroup$ – zijuexiansheng Apr 24 '13 at 8:30
  • $\begingroup$ @zijuexiansheng: $a_{n+1} = a_n + \frac{1}{n+1}, a_1 =1$ is pretty neat too... :-) It has been well known for centuries, yet there is no known "simple" formula for it. btw, I am not claiming that there isn't one for your problem. There might be. Just that it is unlikely. $\endgroup$ – Aryabhata Apr 24 '13 at 8:50
  • $\begingroup$ @Aryabhata Wow, I don't know that. Thank you very much. $\endgroup$ – zijuexiansheng Apr 24 '13 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.