3
$\begingroup$

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{, if $j = 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?

  • 1
    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.2012-05-15
  • 0
    @CameronBuie, typos corrected.2012-05-15

1 Answers 1

1

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

  • 0
    Good idea of using $\pmod{5}$.2012-05-15