Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:








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






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|cite|improve this question
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
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|cite|improve this answer
Good idea of using $\pmod{5}$. – anonymous May 15 '12 at 19:38

Your Answer


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.