4
$\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?

  • 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