Solving for n = 4 in recurrence relation

I am going through 'Concrete Mathematics' by Knuth et al. There is a question that asks one to find the closed form for a recurrence relation defined as follows:

$$Q_{0} = \alpha; \\ Q_{1} = \beta; \\ Q_{n} = \frac{1+Q_{n-1}}{Q_{n-2}}, n > 1$$

We are told to assume that $$\forall n \geq 0, Q_{n} \neq 0$$. We are also provided with a hint, saying that $$Q_{4} = \frac{1+\alpha}{\beta}$$.

This is my question: How do the authors get that value for $$Q_{4}$$? I've tried multiple times to obtain that result, but I end up with $$Q_{4} = \frac{\alpha + \alpha\beta + \beta + 1}{\beta(\beta + 1)}$$, since $$Q_{2} = \frac{1+\beta}{\alpha}$$ and $$Q_{3} = \frac{1 + \alpha + \beta}{\beta}$$.

• Can you factorise $\alpha+\alpha\beta+\beta+1$? Feb 13 '19 at 4:15
• your $Q_4 = \frac{(1+\alpha)(1+\beta)}{\beta(1+\beta)}$ Feb 13 '19 at 4:15
• Ah, of course. Thank you, it's been a while since I've done some math. Feb 13 '19 at 4:52
• @WillJagy. How to prove that this is cyclic ? Feb 13 '19 at 5:57
• @ClaudeLeibovici, you can prove it by induction on n. This will require 5 different cases. When n is 0 mod 5, 1 mod 5, 2 mod 5, 3 mod 5, and 4 mod 5. However, these cases are all extremely similar. Feb 17 '19 at 18:46

In order to get a closed-form from a recurrence relation, you usually start by writing out the first few values until you think you see the closed-form pattern that obtains, and then you try to prove that this form is correct using a proof by induction. In this particular case the sequence is periodic, so the inductive step merely involves verifying the transitions through each of the periodic outcomes.

Finding the periodic values: We have:

\begin{aligned} Q_0 &= \alpha \\[12pt] Q_1 &= \beta \\[10pt] Q_2 &= \frac{1+\beta}{\alpha} \\[6pt] Q_3 &= \frac{1+\alpha+\beta}{\alpha \beta} \\[6pt] Q_4 &= \frac{1+\alpha}{\beta}\\[6pt] Q_5 &= \alpha \\[12pt] Q_6 &= \beta \\[12pt] &\text{ } \text{ } \vdots \\[6pt] \end{aligned}

We can see that $$(Q_5, Q_6) = (Q_0, Q_1)$$ and so we are back to the starting values of the series. Since this is a second-order recursion, the series must repeat these values over and over again. Hence, this is a periodic series with a period of five outcome, and the closed form for the series is:

$$Q_k = \begin{cases} \alpha & & \text{for } k \text{ mod } 5 = 0, \\[6pt] \beta & & \text{for } k \text{ mod } 5 = 1, \\[6pt] (1+\beta)/\alpha & & \text{for } k \text{ mod } 5 = 2, \\[6pt] (1+\alpha+\beta)/\alpha \beta & & \text{for } k \text{ mod } 5 = 3, \\[6pt] (1+\alpha)/\beta & & \text{for } k \text{ mod } 5 = 4. \\[6pt] \end{cases}$$