Solving for n = 4 in recurrence relation

Question

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

Ah, of course. Thank you, it's been a while since I've done some math. — orbit-stabilizer, Feb 13 '19 at 04:52
@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. — orbit-stabilizer, Feb 17 '19 at 18:46

score 0 · Answer 1 · answered Feb 13 '19 at 06:07

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{equation} \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} \end{equation}$$

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

Thanks for your answer, but you're answering a question that was not asked. — orbit-stabilizer, Feb 17 '19 at 18:47

Solving for n = 4 in recurrence relation

1 Answers1