0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Can you factorise $\alpha+\alpha\beta+\beta+1$? $\endgroup$
    – David
    Feb 13 '19 at 4:15
  • 2
    $\begingroup$ your $Q_4 = \frac{(1+\alpha)(1+\beta)}{\beta(1+\beta)}$ $\endgroup$
    – Will Jagy
    Feb 13 '19 at 4:15
  • $\begingroup$ Ah, of course. Thank you, it's been a while since I've done some math. $\endgroup$ Feb 13 '19 at 4:52
  • $\begingroup$ @WillJagy. How to prove that this is cyclic ? $\endgroup$ Feb 13 '19 at 5:57
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 17 '19 at 18:46
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, but you're answering a question that was not asked. $\endgroup$ Feb 17 '19 at 18:47
  • $\begingroup$ Sorry, misread what you were after. $\endgroup$
    – Ben
    Feb 17 '19 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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