Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Cameron Buie May 15 '12 at 19:29
    
@CameronBuie, typos corrected. –  anonymous May 15 '12 at 19:39

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Good idea of using $\pmod{5}$. –  anonymous May 15 '12 at 19:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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