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$
$\endgroup$
-
$\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
$\begingroup$
$\endgroup$
$$\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.
answered Apr 24 '13 at 7:28
-
$\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
