why $\frac{f_n}{f_kf_{n-k}}$ is an integer for this sequence

At the heart of the problem is a lemma about linear recurrences:

Lemma 1. For all $n \geq 0$ and $k > 0$ we have $$a_{n+k} = a_k a_{n+1} + s a_{k-1} a_{n}.$$

Proof of Lemma 1. For any fixed value of $k$, this is true for $n=0$ because $a_k = a_k a_1 + s a_{k-1} a_0$, and for $n = 1$ similarly. Now we can prove it for all $n$ by straightforward induction on $n$. $\square$

There's a corollary I don't strictly need here, but want to mention for completeness; the Art of Problem Solving post you linked to (or Exercise 86 from Chapter 6 of Concrete Mathematics) would now solve the problem, if only we had $\gcd(r,s)=1$. Feel free to skip it.

Corollary 1. If $\gcd(r,s)=1$, then $a_n$ is a strong divisibility sequence: for all $n$ and $k$, we have $$\gcd(a_n, a_k) = a_{\gcd(n,k)}.$$

Proof of Corollary 1. We need $\gcd(r,s)=1$ for two reasons. First, to have $\gcd(a_n, s) = 1$ for all $n > 0$, which follows by induction: $$\gcd(a_n, s) = \gcd(r a_{n-1} + s a_{n-2}, s) = \gcd(a_{n-1}, s)$$ and $\gcd(a_2,s)=1$. Second, to have $\gcd(a_n, a_{n-1}) = 1$ for all $n$, which now also follows by induction: $$\gcd(a_n, a_{n-1}) = \gcd(r a_{n-1} + s a_{n-2}, a_{n-1}) = \gcd(s a_{n-2}, a_{n-1}) = \gcd(a_{n-2}, a_{n-1})$$ and $\gcd(a_1, a_2) = 1$.

Now we can prove Corollary 1. Without loss of generality, $n > k$, and by Lemma 1, we have $$\gcd(a_n, a_k) = \gcd(a_k a_{n-k+1} + s a_{k-1} a_{n-k}, a_k) = \gcd(a_{n-k}, a_k)$$ (note that we can get rid of the $s$ and the $a_{k-1}$ by the two claims above). Now we can just run the Euclidean algorithm in the subscripts, until we get to $\gcd(a_d, a_0) = a_d$. $\square$

By analogy with the $q$-binomial coefficient, we define the $a$-coefficient $\binom{n}{k}_a$ to be the quantity $\frac{f_n}{f_k f_{n-k}}$. We could prove that $\binom{n}{k}_a$ is always an integer, and complete the problem, by messy prime factor work, but that's not how we do it for the actual binomial coefficient! For that, we use Pascal's identity instead. A Pascal-like identity also holds here.

Lemma 2. For $0 < k < n$, $\binom{n}{k}_a = a_{n-k+1} \binom{n-1}{k-1}_a + s a_{k-1} \binom{n-1}{k}_a$.

Proof of Lemma 2. It follows from the definition that $ \binom{n}{k}_a = \frac{a_n}{a_k} \binom{n-1}{k-1}_a = \frac{a_n}{a_{n-k}} \binom{n-1}{k}_a$. From Lemma 1, it follows that $a_n = a_k a_{n-k+1} + s a_{k-1} a_{n-k}$, or $\frac{a_k a_{n-k+1}}{a_n} + \frac{s a_{k-1} a_{n-k}}{a_n} = 1$. So we can take the weighted average $$\binom{n}{k}_a = \frac{a_k a_{n-k+1}}{a_n} \binom{n}{k}_a + \frac{s a_{k-1} a_{n-k}}{a_n} \binom{n}{k}_a$$ and, by substitution, get $$\binom{n}{k}_a = a_{n-k+1} \binom{n-1}{k-1}_a + s a_{k-1} \binom{n-1}{k}_a. \square$$

Now the actual result we want, that $\binom{n}{k}_a$ is always an integer, follows from the observation that $\binom{n}{0}_a = \binom{n}{n}_a = 1$ is always an integer and by induction on $n$.