Problem Statement

Origin Tokyo University entrance exam, science branch, 2001 first semester, problem 4. I got this problem from a Facebook page on Todai math entrance exams.

Consider points $a_1,a_2,\dots$ in the complex plane defined by $a_1 = 1$, $a_2 = i$, and $a_{n+2} = a_{n+1} + a_n$ for $n \geq 1$. Also define $b_n = a_{n+1}/a_n$.

(1) Find the radius of the circle $C$ that passes through points $b_1$, $b_2$, and $b_3$.

(2) Prove that all points $b_n$ ($n = 1,2,\dots$) lie on $C$.

Solution

Let's plot the first few values of $b_n$:

By extreme eyeballing, $\triangle b_1b_2b_3$ looks like a 45-45-90 triangle, which would make $\frac{1}{2}$ the center of $C$. This is not hard to check:

$$b_3 - \frac{1}{2} = 1 + \frac{i}{2} = i\nail{\frac{1}{2} - i} = i\nail{b_2 - \frac{1}{2}}$$$$b_1 - \frac{1}{2} = i - \frac{1}{2} = i\nail{1 + \frac{i}{2}} = i\nail{b_3 - \frac{1}{2}}$$

(1) The radius of $C$ is $\norm{b_1 - \frac{1}{2}} = \frac{\sqrt{5}}{2}$.

(2) Let's write the recurrence relation for $b_n$:

$$\begin{aligned} a_{n+2} &= a_{n+1} + a_n \\ \frac{a_{n+2}}{a_{n+1}} &= 1 + \frac{a_n}{a_{n+1}} \\ b_{n+1} &= 1 + \frac{1}{b_n} \end{aligned}$$

We now prove by induction. Suppose $b_n$ is on $C$; i.e., $\norm{b_n - \frac{1}{2}} = \frac{\sqrt{5}}{2}$. Then

$$\begin{aligned} \nail{b_n - \frac{1}{2}}\nail{\bar b_n - \frac{1}{2}} &= \frac{5}{4} \\ b_n\bar b_n - \frac{1}{2}b_n - \frac{1}{2}\bar b_n - 1 &= 0 \\ -1 + \frac{1}{2\bar b_n} + \frac{1}{2b_n} + \frac{1}{b_n\bar b_n} &= 0 \\ \nail{\frac{1}{b_n} + \frac{1}{2}}\nail{\frac{1}{\bar b_n} + \frac{1}{2}} &= \frac{5}{4} \end{aligned}$$

So $\norm{\frac{1}{b_n} + \frac{1}{2}} = \frac{\sqrt{5}}{2}$, which means $\frac{1}{b_n}$ transforms $b_n$ to a point on another circle $C'$ centered at $-\frac{1}{2}$ with radius $\frac{\sqrt{5}}{2}$. Adding $1$ transforms the point back to $C$, so $b_{n+1} = 1 + \frac{1}{b_n}$ lies on $C$, and we are done.

Epilogue

The two circles and the phasing of points reminded me of a certain Touhou spellcard belonging to a rabbit girl, which is fitting for the Fibonacci-like recurrence.