Sorry for the revive, but here is another solution, albeit heavier on citations but easier to come up with. First of all we can WLOG $\gcd(r,s) = 1$, as this only strengthens the conclusion. Now it is easy to show $\gcd(a_n,a_m) = a_{\gcd(n,m)}$. From here by China TST 2009 Quiz 6 Problem 3 we have there exists a unique sequence of integers $b_i$ such that $a_n = \prod_{d|n} b_d$. Now continue using the exact same method as here to get the result. EDIT : Shoot darn wait this does not quite work as setting $\gcd(r,s) = 1$ does not strengthen the conclusion. In this case everything works out except the prime divisors of $\gcd(r,s)$... anyone see any easy patch to this?

Hmm we had the $r=s=1$ case for this problem on our 15-251 (Great Theoretical Ideas in Computer Science) homework! Anyway, a solution somewhat simpler than the above two. I claim that \[a_n=a_ka_{n-k+1}+sa_{k-1}a_{n-k}\]for all positive integers $1\leq k \leq n$. The proof follows by induction; the base case trivially holds, and for the inductive step, write \begin{align*}a_n&=a_ka_{n-k+1}+sa_{k-1}a_{n-k}=a_k(ra_{n-k}+sa_{n-k-1})+sa_{k-1}a_{n-k}\\&=a_{n-k}(ra_k+sa_{k-1})+sa_ks_{n-k-1}=a_{n-k}a_{k+1}+sa_ks_{n-k-1}.\end{align*}Next, denote $b_{n,k}=\tfrac{f_n}{f_kf_{n-k}}$. Note that $b_{1,n}=\tfrac{f_n}{f_1f_{n-1}}=a_n$ and $b_{n-1,n}=\tfrac{f_n}{f_{n-1}f_1}=a_n$ are both integers. Now note that with the use of our lemma above (with shifted indeces, oops!) we get \begin{align*}a_{n-k+1}\cdot \dfrac{f_n}{f_kf_{n-k}}+sa_{k}\dfrac{f_n}{f_{k+1}f_{n-k-1}}&=f_n\left(\dfrac{a_{n-k+1}}{f_kf_{n-k}}+\dfrac{sa_k}{f_{k+1}f_{n-k-1}}\right)\\&=f_n\left(\dfrac{a_{n-k+1}a_{k+1}+ sa_{k}a_{n-k}}{f_{k+1}f_{n-k}}\right)\\&=f_n\cdot\dfrac{a_{n+1}}{f_{k+1}f_{n-k}}=\dfrac{f_{n+1}}{f_{k+1}f_{n-k}}.\end{align*}This means that $a_{n-k+1}b_{n,k}+sa_kb_{n,k+1}=b_{n+1,k+1}$, and combining this with our reasoning above (e.g. by induction on $n$) we get that all the $b_{n,k}$ are integers as well. We are done. $\blacksquare$ The main idea behind the above solution is that working with things in terms of divisibility seems to be really hard for this problem (although tanh's solution above attacks in this manner somewhat successfully), and so we need to search for other manners to prove the desired expression is always an integer. After experientation with binomial coefficients, one comes up with the idea of generalizing Pascal's Identity - $\textstyle\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$ - to arbitrary linear sequences and then simply crafting the algebra so that everything works out.

Zhero wrote: 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 $\displaystyle\frac{f_n}{f_kf_{n-k}}$ is an integer for all integers $n$ and $k$ such that $0 < k < n$. Evan O' Dorney. Is this correct?? Claim:-Let $u_n \in \mathbb{N}$ be a sequence of elements such that $u_1=1,u_2=a$ and $u_n=au_{n+1}+bu_n$ then there exists a polynomial $P(x)$ s.t $u_n=\prod _{d|n } P(d)$ Proof:-We can use Lagrange Interpolation+Strong induction to construct $P(n)$ in the following way:-If we have already constructed $P(n)$ then we will construct $P(n+1)$ in the following way: $\bullet $ If $n+1$ is a prime then $P(n+1)=u_{n+1}$ $\bullet$ If $n+1$ is not prime $=\prod p_i^{a_i}$ then we can use note that if $f(n)=\prod g(n)a(n)$ then $f(n)$ is multiplicative.So we need to construct $a(n)$ and $g(n)$ s.t $u_{n+1}=\prod_{d|n} g(d) \prod_{d|n} a(n)$.Let $\omega$ be a primitive root of unity modulo $p=q_i$ where $v_{q_i}(u_n)=b_i$.First I will construct $g(n)$.Notice that we need $v_p(\prod(g(n))=b_i$.Since $g(n) \in \mathbb{N}$(we will prove this in the next claim) this turns out to be finding no of $g(n)$ divisible by $p$ i.e if $k$ is the least number such that $p|g(k)$ then $v_p(\prod g(n))$ becomes $=\text{no of d which is k modulo p}+………$ by Hensel’s Lemma.I will prove such a polynomial $M(x)$ exists. Consider $\Phi_p(x)=\prod (x-\text{all roots of unity})=\prod (x-\omega^n)$.By Lagrange Interpolation we can construct $M(x)=b_i-\max \Phi_j(x) \text{with highest vp less than } b_i$.So $g(x)a(x)=\prod M_i(x)$ works.$\blacksquare$ Claim:-$P(x) \in \mathbb{N}[X]$ Proof:-We can use cyclotomic polynomials again for this.

$\blacksquare$

djmathman wrote: I claim that \[a_n=a_ka_{n-k+1}+sa_{k-1}a_{n-k}\]for all positive integers $1\leq k \leq n$. The proof follows by induction; the base case trivially holds, and for the inductive step, write \begin{align*}a_n&=a_ka_{n-k+1}+sa_{k-1}a_{n-k}=a_k(ra_{n-k}+sa_{n-k-1})+sa_{k-1}a_{n-k}\\&=a_{n-k}(ra_k+sa_{k-1})+sa_ks_{n-k-1}=a_{n-k}a_{k+1}+sa_ks_{n-k-1}.\end{align*} How is the inductive step correct? You're saying that $a_n = a_ka_{n-k+1} + sa_{k-1}a_{n-k}$... so you basically used the claim in the proof of the claim! I might be wrong, but can someone please explain how the inductive step works?

I'm using induction on $k$, not on $n$. (Probably could have been a bit clearer here, sorry.) The base case of $k = 1$ reads \[ a_n = a_1a_n + sa_0a_n, \]which holds since $a_1 = 1$ and $a_0 = 0$. For the inductive step, I start with the statement \[ a_n=a_ka_{n-k+1}+sa_{k-1}a_{n-k} \]and use that to prove that \[ a_n = a_{k+1}a_{n-k} + sa_ks_{n-k-1}. \]

@above I still don't get one thing. Using the induction, you ending up proving \[ a_n = a_{k+1}a_{n-k} + sa_ks_{n-k-1}. \] while you want to prove \[ a_n=a_ka_{n-k+1}+sa_{k-1}a_{n-k} \]...

Those are the same thing, except in the first equation, $k$ is replaced by $k+1$. This is pretty consistent with how lots of people do induction proofs, where you show that, if the thing hold for $k$, then it also holds for $k+1$. (But some people will go from $k-1$ to $k$ instead, partially for these reasons.)

djmathman wrote: Those are the same thing, except in the first equation, $k$ is replaced by $k+1$. This is pretty consistent with how lots of people do induction proofs, where you show that, if the thing hold for $k$, then it also holds for $k+1$. (But some people will go from $k-1$ to $k$ instead, partially for these reasons.) Oh ok. I know what induction is.. it just looks like i was just being dumb

Set $a_n = c_1\alpha^n + c_2 \beta^n$ where $\alpha, \beta \in \mathbb F_{p^2}$. By considering $a_0$ and $a_1$ we get $$a_n = \frac{\alpha^n - \beta^n}{\alpha-\beta}.$$The desired ratio equals $$\frac{f_n}{f_kf_{n-k}} =\frac{(\alpha^{k+1}-\beta^{k+1}) \cdots (\alpha^n - \beta^n)}{(\alpha-\beta)\cdots (\alpha^{n-k}-\beta^{n-k})}.$$Now we do something similar to $\nu_p$: consider any cyclotomic polynomial of degree $d$. It divides exactly $\left \lfloor \frac{n-k}d \right \rfloor$ terms on the bottom and at least that many on the top. This implies that $\frac{f_n}{f_kf_{n-k}}$ is an algebraic integer, and as all the $a_i$ are integers, it must be an integer too.

Let $\alpha=\frac{r+\sqrt{r^2+4s}}{2}$ and $\beta=\frac{r-\sqrt{r^2+4s}}{2}$. We would then have $$a_n=\frac{1}{\sqrt{r^2+4s}}(\alpha^n-\beta^n).$$ In the fraction, the constant factor cancels, so we are left with $$\frac{\prod_{r=n-k+1}^n \alpha^r-\beta^r}{\prod_{r=1}^k \alpha^r-\beta^r}$$ We claim that the denominator divides the numerator, that is, this is an integer polynomial. Let $\Phi_n(x,y)$ be the polynomial defined by $\Phi_1(x,y)=x-y$ and $x^n-y^n=\prod_{d\mid n}\Phi_d(x,y)$ (essentially, the cyclotomic polynomials but with $1$ as a "variable" as well). Thus, for any $m$, the exponent of $\Phi_m(\alpha,\beta)$ in the denominator is $\lfloor \frac{k}{m}\rfloor$ (since only when $r$ is a multiple of $m$ does it have a factor). However, they key idea is that any $k$ consecutive positive integers has at least $\lfloor \frac{k}{m}\rfloor$ multiples of $k$, so the exponent of $\Phi_m(\alpha,\beta)$ is at least $\lfloor \frac{k}{m}\rfloor$. Repeating this for all $m$, we see that this becomes an integer polynomial in $\alpha,\beta$. Furthermore, this is symmetric in $\alpha,\beta$, so it is a symmetric integer polynomial. Thus, by Vieta's, it can be expressed as an integer polynomial in $r$ and $s$ since $\alpha$ and $\beta$ are the roots to $x^2-rx-s=0$, done.

Storage: Let $\alpha, \beta$ denote the roots of $x^2-rx-s=0$. Thus, since $a_0=0, a_1=1$, we have: $a_n = \frac{\alpha^n - \beta^n}{\alpha-\beta}$. We want to prove that: $$\prod_{t=1}^{k} \frac{\alpha^t-\beta^t}{\alpha-\beta} | \prod_{t=n-k+1}^{n} \frac{\alpha^t-\beta^t}{\alpha-\beta}$$Note that: it suffice to show: $$\prod_{t=1}^{k} \frac{x^t-1}{x-1}|\prod_{t=n-k+1}^{n} \frac{x^t-1}{x-1}.$$ Note that, $\frac{x^t-1}{x-1} = \prod_{d|t} \Phi_{d}(x)$. Thus, using this identity, its evidently true that the above identity holds as: The number of elements divisible by $n$ in set $\{1, 2, \cdots, k \}$ is $\lfloor k/n \rfloor$. But the number of elements divisible by $n$ in $\{n-k + 1, n-k + 2, \dots, n\}$ is at-least $\lfloor k/n \rfloor$ and we are done.