More fun in 2015, Part 15

With problems like this we generally look to find a closed form for the sequences $a_n$ and $b_n$ . However, since we need only find $\frac{b_{2015}}{a_{2015}}$ it can sometimes be easier to find a closed form for the sequence $\frac{b_n}{a_n}$ . We begin with the recurrence relation: $\begin{aligned} \frac{b_n}{a_n} &= \frac{b_{n-1}a_{n-2} + a_{n-1}b_{n-2}}{a_{n-1}a_{n-2} - b_{n-1}b_{n-2}} \\ &= \frac{\frac{b_{n-1}}{a_{n-1}} + \frac{b_{n-2}}{a_{n-2}}}{1 - \frac{b_{n-1}b_{n-2}}{a_{n-1}a_{n-2}}} \end{aligned}$ This has the structure of the angle sum formula for $\tan$ . Since the range of $\tan$ is $\mathbb{R}$ , let $\frac{b_n}{a_n} = \tan\theta_n$ , and then we have: $\begin{aligned} \frac{b_n}{a_n} = \tan\theta_n &= \frac{\tan\theta_{n-1} + \tan\theta_{n-2}}{1 - \tan\theta_{n-1}\tan\theta_{n-2}} \\ &= \tan(\theta_{n-1} + \theta_{n-2}) \end{aligned}$ That is, the sequence $\theta_n = \theta_{n-1} + \theta_{n-2}$ , and since $\frac{b_1}{a_1} = \frac{b_2}{a_2} = 1$ this sequence starts with $\theta_1 = \theta_2 = \frac{\pi}{4}$ . This satisfies the same recurrence relation as the Fibonacci numbers, and so $\theta_n = F_n\frac{\pi}{4}$ , where $F_n$ is the nth Fibonacci number.

Thus $\frac{b_{2015}}{a_{2015}} = \tan\left(F_{2015}\frac{\pi}{4}\right)$ . Since $\tan$ has a period of $\pi$ , we need only calculate $F_{2015} \bmod 4$ . The Fibonacci numbers, modulo 4 are: $1, 1, 2, 3, 1, 0, 1, 1, \ldots$ Since this sequence is periodic with period 6, and $2015 \equiv 5 \pmod 6$ , we have $F_{2015} \bmod 4 = 1$ . Thus: $\frac{b_{2015}}{a_{2015}} = \tan\frac{\pi}{4} = \boxed{1}$

Consider the sequence $\{c_n\}$ formed as $c_n = a_n + b_n i$ (where $i$ is the imaginary unit). Observe that

$\begin{aligned} c_{n+2} &= a_{n+2} + b_{n+2} i \\ &= (a_{n+1} a_n - b_{n+1} b_n) + (b_{n+1} a_n + a_{n+1} b_n) i \\ &= a_{n+1} a_n + (b_{n+1} i) (b_n i) + a_n (b_{n+1} i) + a_{n+1} (b_n i) \\ &= (a_{n+1} + b_{n+1} i) (a_n + b_n i) \\ &= c_{n+1} c_n \end{aligned}$

This looks like the Fibonacci recurrence, but in product form (the $(n+2)$ -th term is the product of the $(n+1)$ -th term and the $n$ -th term instead of their sum). In fact, since $c_1 = c_2 = (1+i)$ , we can show by simple induction that $c_n = (1+i)^{F_n}$ , where $F_n$ is the $n$ -th Fibonacci number. (The base case $n = 1, 2$ is trivial; $c_{n+2} = c_{n+1} c_n = (1+i)^{F_{n+1}} (1+i)^{F_n} = (1+i)^{F_{n+1}+F_n} = (1+i)^{F_{n+2}}$ .)

All complex numbers can be represented in polar coordinates as $r \text{cis } \theta = r \cos \theta + r \sin \theta \cdot i$ for suitable $r, c$ . Note that $c_{2015} = a_{2015} + b_{2015} i$ , thus $a_{2015} = r \cos \theta, b_{2015} = r \sin \theta$ , and so $\frac{b_{2015}}{a_{2015}} = \frac{r \sin \theta}{r \cos \theta} = \tan \theta$ . Thus it suffices to determine the argument $\theta$ . Moreover, since we only care about $\tan \theta$ and $\tan$ is periodic modulo $\pi = 180^\circ$ , it suffices to compute $\theta \mod 180^\circ$ . (Here $a \mod b$ means a real $r$ , $0 \le r < b$ , such that $\frac{a-r}{b}$ is an integer. Also, I use degrees instead of radians because it's easier to type. Sheesh.)

For a complex number $z = r \text{ cis } \theta$ , remember that $z^n = r^n \text{ cis } n \theta$ . In our case, $c_{2015} = (1+i)^{F_{2015}} = (\sqrt{2} \text{ cis } 45^\circ)^{F_{2015}}$ , so $c_{2015} = (\sqrt{2})^{F_{2015}} \text{ cis } F_{2015} \cdot 45^\circ$ . Thus $\theta = F_{2015} \cdot 45^\circ$ .

We need to compute $\theta \mod 180^\circ$ . However, we know that $45^\circ$ divides $\theta$ , thus we can move it out:

$\begin{aligned} \theta \mod 180^\circ &= (F_{2015} \cdot 45^\circ) \mod (4 \cdot 45^\circ) \\ &= 45^\circ \cdot (F_{2015} \mod 4) \end{aligned}$

Thus it suffices to compute $F_{2015} \mod 4$ .

Observe that the Fibonacci sequence modulo $4$ is periodic with period $6$ : $1, 1, 2, 3, 1, 0, 1, 1, \ldots$ . After $1, 1$ occurs again, the entire sequence is guaranteed to be periodic, since the Fibonacci sequence only depends on the previous two terms. Thus we know that $F_{n+6} \equiv F_n \pmod 4$ .

This way, we know that $2015 = 335 \cdot 6 + 5$ , so $F_{2015} \equiv F_{5} \equiv 1 \pmod 4$ . Thus $\theta = 45^\circ \cdot 1 = 45^\circ$ , and $\frac{b_{2015}}{a_{2015}} = \tan \theta = \tan 45^\circ = \boxed{1}$ .