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