ELMO 2010 Problem 2

Let $r$ and $s$ be positive integers. Define $a_0 = 0$ , $a_1 = 1$ , and $a_n = ra_{n-1} + sa_{n-2}$ for $n \geq 2$ . Let $f_n = a_1a_2\cdots a_n$ . Prove that $\frac{f_n}{f_kf_{n-k}}$ is an integer for all integers $n$ and $k$ such that $0 < k < n$ .

Evan O' Dorney.