An IMO $1986$ sequence

Question

I have been stuck on this problem for some time, but I don't have any idea as to where to start. The problem is as follows:

Let $(a_{n\in \mathbb N})$ be the sequence of integers defined recursively by $$a_0 =0, a_1 =1, a_{n+2} = 4a_{n+1} +a_n$$ Find the common divisors of $a_{1986}$ and $a_{6891}$.

Any help is appreciated. Thank you.

Answer 1

One can show inductively that $(u_n,u_{n+1})=1$ and $$ u_{m}=u_{k}u_{m-k+1}+u_{k-1}u_{m-k},\tag{1} $$ whenever $\,k,m\in\mathbb N$ and $k< m$.

Suppose now that (Euclidean division) $$ m=\ell k+\upsilon, \quad \upsilon\in\{0,1,\ldots,k-1\}, $$ then it is readily shown, a consequence of $(1)$ that $$ (u_m,u_k)=(u_k,u_\upsilon). \tag{2} $$

Using $(2)$ repeatedly we obtain that $$ (u_m,u_k)=u_{(m,k)}, $$ and as $(6891,1986)=3$, then $$ (u_{6891},u_{1986})=u_3=4. $$

Answer 2

Just a Hint to start:

The characteristic equation is $$x^2-4x-1=0$$ the roots are $$r_1=2+\sqrt{5} \;\;r_2=2-\sqrt{5}$$

thus

$$a_n=Ar_1^n+Br_2^n$$ with $a_0=A+B=0$ and $Ar_1+Br_2=1$

$\implies A=\frac{1}{2\sqrt{5}}=-B$.