2016 AMC 12B Problems/Problem 25

Problem

The sequence $(a_n)$ is defined recursively by $a_0=1$ , $a_1=\sqrt[19]{2}$ , and $a_n=a_{n-1}a_{n-2}^2$ for $n\geq 2$ . What is the smallest positive integer $k$ such that the product $a_1a_2\cdots a_k$ is an integer?

$\textbf{(A)}\ 17\qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 19\qquad\textbf{(D)}\ 20\qquad\textbf{(E)}\ 21$

Solution

Let $b_i=19\text{log}_2a_i$ . Then $b_0=0, b_1=1,$ and $b_n=b_{n-1}+2b_{n-2}$ for all $n\geq 2$ . The characteristic polynomial of this linear recurrence is $x^2-x-2=0$ , which has roots $2$ and $-1$ . Therefore, $b_n=k_12^{n}+k_2(-1)^n$ for constants to be determined $k_1, k_2$ . Using the fact that $b_0=0, b_1=1,$ we can solve a pair of linear equations for $k_1, k_2$ :