Could I have some hints on the following problem (British mathematical Olympiad Round 2, 2020 Q4)
A sequence $b_1, b_2, b_3, . . .$ of nonzero real numbers has the property that
$$b_{n+2}=\frac{b_{n+1}^2-1}{b_n}$$
for all positive integers n.
Suppose that $b_1 = 1$ and $b_2 = k$ where $1 < k < 2$.
(i) Show that there is some constant $B$,
depending on $k$, such that $−B ≤ b_n ≤ B$ for all $n$.
(ii) Show that, for some $1 < k < 2$, there
is a value of n such that $b_n > 2020$.
I don't really have much ideas for part (i). I tried analysing the sequence $b_{n+1} – b_n$ but I didn't get too far.
For part (ii) if we set $k=2$ each term of $b_n$ are consecutive integers so i think showing there exists some left limit ${k\nearrow 2}$ then it might prove the result.
Best Answer
Putting together a few things from the various provided links, I think I can help without leaving out too many steps--other than some tedious algebraic manipulation.
Given the following recurrence: $$b_{n+2} = \frac{b_{n+1}^2-1}{b_n} \tag1\label1$$ we wish to prove $$ \begin{gather} (\exists B(k))(\forall n |b_n| < B(k)) \tag{A}\label{A} \\[1ex] 1 < k < 2 \implies (\exists n)(b_n > 2002) \tag{B}\label{B} \end{gather} $$ First, we can rearrange the recurrence a bit to get $$b_nb_{n+2}-b_{n+1}^2 = -1 \tag2\label\2$$ The LHS expression is equal to $-1$ for all $n$, so we can look at two consecutive iterations and set them equal: $$ \begin{align} &b_nb_{n+2} - b_{n+1}^2 = b_{n-1}b_{n+1} - b_n^2 \implies \\[1ex] &b_n(b_{n+2} + b_n) = b_{n+1}(b_{n-1} + b_{n+1}) \implies \\[1.5ex] &\frac{b_{n+2} + b_n}{b_{n+1}} = \frac{b_{n+1} + b_{n-1}}{b_{n}} = \frac{b_n + b_{n-2}}{b_{n-1}} = \cdots = \frac{b_1+b_3}{b_2} = \frac{1+k^2-1}{k}= k\tag3\label3 \end{align} $$ That quotient is true for all $n$ as well, but it's still a recurrence, and we can rewrite it as: $$b_{n+2} - kb_{n+1} + b_n = 0 \tag4\label4$$ Now this part I'm not clear on personally, but with recurrences, if you can write equations of this form for the recurrence, you can convert the equation to a characteristic polynomial by substituting $x^i$ for $b_{n+i}$. Here, that gives us $$x^2 - kx + 1 = 0 \tag5\label5$$ The complex roots of this equation are $(r,s) = (\frac12 (k + z), \frac12(k-z))$, where $z$ is the complex square root $z = \sqrt{k^2-4}$. The really cool thing about these recurrences is that with the roots of the polynomial in hand, we can write an explicit expression for $b_n$: $$b_n = cr^n + ds^n \implies b_n = c\left(\frac{k+z}{2}\right)^n + d\left(\frac{k-z}{2}\right)^n \tag6\label6$$ where $c$ and $d$ are constants based on the initial conditions. We know $b_1 = 1, b_2 = k$, so we can create a system of equations: $$ \left\{ \begin{array}{ll} \frac12 c(k+z) + \frac12 d(k-z) &=2 \\[0.5ex] \frac14 c(k+z)^2 + \frac14 d(k-z)^2 &=4k \\ \end{array} \right. $$ The solution to the system is $c = \frac1z, d=-\frac1z$. So our final explicit equation is: $$b_n = \frac1z \left(\left(\frac{k+z}{2}\right)^n - \left(\frac{k-z}{2}\right)^n \right) = \frac1z(r^n - s^n) \tag7\label7$$ Now, even though all of the solutions to this (for integer $n$) are real, we can take advantage of the complex nature of the two roots. First, note that $r$ and $s$ are complex conjugates. Adding them together gives $k$, and multiplying them gives $1$. Any time a polynomial has complex roots, they will come in conjugate pairs. We could write our roots a bit differently:
$$r,s = \frac k2 \pm i \sqrt{1-\frac{k^2}{4}} = p \pm iq$$
We often plot complex numbers as vectors on the complex plane, pointing away from the origin to the point $(p,q)$. Now this is cool: the distance formula works with complex numbers, giving the magnitude of the vector as $|p+iq| = \sqrt{p^2+q^2}$. But conveniently for our use, we have:
$$|r| = \sqrt{\left(\frac k2\right)^2 + 1-\frac{k^2}{4}} = \sqrt{\frac{k^2}{4} + 1-\frac{k^2}{4}} = 1$$
The same will be true for $s$, as complex conjugates have the same magnitude. This is a unit vector, so its end lies on the unit circle. And that's really convenient. When you multiply two complex numbers, you cause a rotation: you multiply the magnitudes, but add the angles (from the positive $x$ axis) of the two vectors. But if you multiply two unit vectors, with magnitude $1$, the product will still have magnitude $1$--it will merely have rotated partway around the unit circle.
And since exponentiation is just repeated multiplication, each higher power is just a further rotation around the circle. Complex conjugates have the same angle but reflected around the $x$ axis, so $r^n$ and $s^n$ will always remain complex conjugates.
OK, we're almost there. Remember we wrote $(r,s) = p \pm iq$ earlier. Since the complex vectors all lie on the unit circle, $|p| \le 1, |q| \le 1$. And indeed this will be true for all powers of $r$ and $s$. If we subtract complex conjugates, we get $p+iq - (p-iq) = p-p+iq+iq = 2qi$. Since $|q| \le 1$, $|2qi| \le 2i$.
We have to divide by $z$, which is conveniently imaginary and rids us of the $i$, giving: $$b_n = \frac{2q}{\sqrt{4-k^2}} \implies \color{blue}{|b_n| < \frac{2}{\sqrt{4-k^2}} = B(k)}$$ Which is the request of (A). The request of (B) comes by setting $b_n=2002$: $$2002 < \frac{2}{\sqrt{4-k^2}} \implies 2002^2 < \frac{4}{4-k^2} \implies 2002^2(4-k^2) < 4 \implies k^2 > \frac{4(2002^2-1)}{2002^2}$$
We can see that $k$ will be close to, but necessarily smaller than, $2$. QED.