# Solve the recurrence: $Q_0=\alpha$; $Q_1=\beta$; $Q_n=(1+Q_{n-1})/Q_{n-2}$, for $n>1$.

This one is from "Concrete Mathematics":

Solve the recurrence:

$Q_0=\alpha$; $Q_1=\beta$;

$Q_n=(1+Q_{n-1})/Q_{n-2}$, for $n>1$.

Assume that $Q_n \neq 0$ for all $n \geq 0$.

I have solved it as follows:

$Q_0=\alpha$

$Q_1=\beta$

$Q_2=(1+\beta)/\alpha$

$Q_3=[1+(1+\beta)/\alpha]/\beta=(1+\alpha+\beta)/\alpha\beta$

$Q_4=\frac{[1+(1+\alpha+\beta)/\alpha\beta]}{(1+\beta)/\alpha}=\frac{1+\alpha+\beta+\alpha\beta}{\alpha\beta}\times\frac{\alpha}{1+\beta}=(1+\alpha)/\beta$

$Q_5=(1+Q_4)/Q_3=\frac{1+(1+\alpha)/\beta}{(1+\alpha+\beta)/\alpha\beta}=\frac{1+\alpha+\beta}{\beta}\frac{\alpha\beta}{1+\alpha+\beta}=\alpha$

$Q_6=(1+Q_5)/Q_4=\frac{1+\alpha}{(1+\alpha)/\beta}=\beta$

Because $Q_5=\alpha=Q_0$ and $Q_6=\beta=Q_1$, we can conclude from the recurrence relation that this function is periodic:

$Q_0=Q_5=Q_{10}=\cdots=\alpha$

$Q_1=Q_6=Q_{11}=\cdots=\beta$

$Q_2=Q_7=Q_{12}=\cdots=(1+\beta)/\alpha$

$Q_3=Q_8=Q_{13}=\cdots=(1+\alpha+\beta)/\alpha\beta$

$Q_4=Q_9=Q_{14}=\cdots=(1+\alpha)/\beta$

I will express this relationship in the following way:

For $n=5k+j$, where $k$ is a natural number and $j=0,1,2,3,4$:

\begin{align}Q_{5k+j}&=\begin{cases} \alpha \text{, ifj = 0$} \\ \beta \text{, if$j = 1$} \\ (1+\beta)/\alpha \text{, if$j = 2$} \\ (1+\alpha+\beta)/\alpha\beta \text{, if$j = 3$} \\ (1+\alpha)/\beta \text{, if$j = 4} \end{cases}\end{align}

I couldn't find a simpler solution. Since the question asks "solve the recurrence", I would have expected to find a simpler closed form solution. Is this a good solution for the recurrence?

-
It's okay for closed forms to be defined piecewise. The big thing is to make sure you aren't still defining any terms recursively, which you've accomplished quite nicely. You've misrecorded your calculation of $Q_3$--it should be $[1+(1+\beta)/\alpha]/\beta$--and of $Q_6$--it should be $\cfrac{1+\alpha}{(1+\alpha)/\beta}$--but you did calculate them correctly. – Cameron Buie May 15 '12 at 19:29
@CameronBuie, typos corrected. – anonymous May 15 '12 at 19:39

Yes, this is exactly what’s wanted. It’s a perfectly good closed form: given $n$, it allows you to calculate $Q_n$ directly, without using the recursion. You could make it a little nicer by getting rid of $k$:
\begin{align*} Q_n&=\begin{cases} \alpha \text{, if n\equiv0\pmod5} \\ \beta \text{, if n\equiv1\pmod5} \\ (1+\beta)/\alpha \text{, if n\equiv2\pmod5} \\ (1+\alpha+\beta)/\alpha\beta \text{, if n\equiv3\pmod5} \\ (1+\alpha)/\beta \text{, if n\equiv4\pmod5}\;. \end{cases}\end{align*}
Good idea of using $\pmod{5}$. – anonymous May 15 '12 at 19:38