This was my solution at the contest, can you guys verify this? (My solution was more rigorous than this in the actual contest though)

This took me an hour to write... Need to practice with LATEX more....

WOW! NICE LATEX!!!!!

Let $B_n(x)=P_n(x)/Q_n(x)$. Then, $B_n(x)=\frac{Q_n(x)}{Q_{n+1}^3(x)}\frac{P_{n+1}^3(x)+Q_{n+1}^3(x)}{P_n(x)}$ If $n\ge 3$ then if $B_n(x)=0, B_{n-1}(x)=v$, where $v^3+1=0$, and $B_{n+1}(x)=-v^2$, also a third root of $-1$. So if $z$ is a kth root of $P_n(x)=0$, $z$ is a kth root of $P_{n-1}(x)-vQ_{n-1}(x)=0$, for one of the three possible values of $v$, and also a kth root of $P_{n+1}(x)+v^2Q_{n+1}(x)=0$. Hence $P_n(x)$ divides $P_{n+1}^3(x)+Q_{n+1}^3(x)$. I won't bother to repeat the induction argument that shows that both the Q's and A's are powers of $x$ with Fibonacci exponents.

rkm0959 wrote: Claim 5. If $D_{i}$ are all integers for all $i\le n$, the gcd of $D_{i}$ and $D_{i-1}$ is $1$ for all $i\le n$. Proof of Claim 5. From Claim 4, it suffices to show that gcd of $D_{i}$ and $k$ is 1. This is straightforward by induction and Claim 4. Check that $D_3 = k^3+1$ and the recurrence for $D_{n}$ will finish the proof. $\blacksquare$ I don't think it's true. Take $\gcd \left( D_i,D_{i-1} \right)=2$ with $2 \mid k$ and it still satisfies the condition. We will have $2 \nmid D_3$ but $2 \mid D_i$ with $i \ge 4$. We can prove that $\gcd \left( D_i,D_{i-1} \right) \in \{ 1,2 \}$.

Yep.. I realized that my proof was flawed very recently

rkm0959 wrote: Yep.. I realized that my proof was flawed very recently

Instead of $k$ we can put $x $ and assume that $D_i$ is a polynomial with integer coefficient for each $i$ then we have $\gcd (D_i, D_{i-1})=1$

shinichiman wrote: Claim 7. If $\gcd (D_i,D_{i-1})=2^w$ for $i \ge 5$ then $v_2(D_{i+1})=3v_2(D_i)-v_2(D_{i-1})$ and $v_2(D_{i+1})< C_{i+1}$.

I think $D_5$ should be $(k^3+1)^8+3(k^3+1)^5+3(k^3+1)^2+1$, so $v_2(D_5)$ is at least $3$.

My solution... It is easy to see that $A_n=k^{F_n}$ step 1. Let $B_t=C_t/k^{F_{2t-3}}$,, then we only need to show that $C_n$ is an integer step 2. using the recurrence formular of $B_n$, find the recurrence formular of $C_n$ step 3. using the formular, find $gcd(C_n,C_{n-1})=1$ step 4. Now, by induction we can see that $C_n$ is an integer using the property we proved in step 3.. (It is kind of a bash, but not much... I solved this problem in 30 minutes including bashing)

rkm0959 wrote: Yep.. I realized that my proof was flawed very recently shinichiman wrote: Claim 7. If $\gcd (D_i,D_{i-1})=2^w$ for $i \ge 5$ then $v_2(D_{i+1})=3v_2(D_i)-v_2(D_{i-1})$ and $v_2(D_{i+1})< C_{i+1}$. Some nasty problems with $2$ can be easily solved by dropping $2$ from $k$. More precisely, if we let $k = 2^l m$, $l\geq 0$, $m$ is odd, and $D_n = m^{F_{2n}} B_{n+3}$. Then we get $$D_{n+1} = \frac{D_n^3 + m^{3F_{2n}}}{D_{n-1}}$$Since $m$ is odd, we can prove that $\gcd(D_n,D_{n-1}) = \gcd(D_n,m)=1$ for every non-negative integer $n$ by "rkm0959"'s original arguments. freefrom_i wrote: Instead of $k$ we can put $x $ and assume that $D_i$ is a polynomial with integer coefficient for each $i$ then we have $\gcd (D_i, D_{i-1})=1$ This idea does not work unless additional arguments are provided. To apply this idea on "rkm0959"'s proof directly, we need $P, Q\in\mathbb{Z}[x]$ s.t. $PD_i + QD_{i-1}=1$. But we cannot guarantee that, even though $D_i$ and $D_{i-1}$ don't have any common factor.

Solved with pinetree1. Let $f_n(X)$ be the sequence of rational functions satisfying $f_1=1$, $f_2=X$, and \[f_{n+2}=\frac{f_{n+1}^3+1}{f_n}.\]We have the following key claim. Claim: For each $n$, we have that $f_n$ is actually a Laurent polynomial (i.e. a finite integer linear combination of $X^m$ where $m$ ranges over all integers). Furthermore, $X^Nf_n$ and $X^Nf_{n-1}$ share no non-monomial polynomial factor where $N$ is large enough such that $X^Nf_n$ and $X^N f_{n-1}$ are integer polynomials. Proof: The proof is by induction, with the base cases of $n\le 4$ verified by hand. Now suppose it is true for $1,\ldots,n$, we'll show it for $n+1$. Indeed, we have \[f_{n+1} = \frac{f_n^3+1}{f_{n-1}} = \frac{(f_{n-1}^3+1)^3+f_{n-2}^3}{f_{n-1}f_{n-2}^3}=:\frac{P}{Q}.\]To show that this is a Laurent polynomial, it suffices to show that any polynomial factor of the numerator of $Q$ that is an irreducible polynomial to some power divides the numerator of $P$. Indeed, since the numerators of $f_{n-1}$ and $f_{n-2}$ don't share any factors (by the inductive hypothesis), it suffices to show that $P/f_{n-1}$ and $P/f_{n-2}^3$ are Laurent polynomials. Indeed, we have \[P/f_{n-1} = f_{n-1}^2(3+3f_{n-1}^3+f_{n-1}^6) + \frac{1+f_{n-2}^3}{f_{n-1}} = f_{n-1}^2(3+3f_{n-1}^3+f_{n-1}^6)+f_{n-3},\]which is clearly a Laurent polynomial. Furthermore, \[P/f_{n-2}^3 = 1+f_n^3,\]which is also clearly a Laurent polynomial. Thus, $f_{n+1}$ is a Laurent polynomial. Now we show that $f_{n+1}$ and $f_n$ share no non-monomial factors in their numerator. Indeed, suppose they shared a factor $g$, which is an integer polynomial. We see that \[1=f_{n+1}f_{n-1}-f_n^3,\]so $g$ must divide $1$, which is not possible. This proves the claim entirely. $\blacksquare$ Given the claim, we have the following bound. Claim: Let $a_n$ be the least non-negative integer such that $x^{a_n}f_n$ is an integer polynomial. Then, \[a_{n+1}\le 3a_n-a_{n-1}.\] Proof: We have \[f_{n+1}f_{n-1}=f_n^3+1,\]so \[(f_{n+1}\cdot x^{3a_n-a_{n-1}})\cdot(f_{n-1}\cdot x^{a_{n-1}})=(f_n\cdot x^{a_n})^3 + 1.\]Note that $f_{n-1}\cdot x^{a_{n-1}}$ has nonzero constant term, so if $f_{n+1}\cdot x^{3a_n-a_{n-1}}$ is not a polynomial, then neither is $(f_n\cdot x^{a_n})^3 + 1$, which is clearly false, so $f_{n+1}\cdot x^{3a_n-a_{n-1}}$ is a polynomial. Thus, \[a_{n+1}\le 3a_n-a_{n-1},\]as desired. $\blacksquare$ Now by plugging in $k$ into $f_n$, we see that we'd be done as long as $a_n\le F_{2n}$. We show this now. The main claim is that we can iterate the inequality from the claim to get that \[a_{n+1}\le F_{2k} a_{n-k+2} - F_{2k-2}a_{n-k+1}\]for all $2\le k\le n-2$. Indeed, taking $k=n-2$ gives the desired result since $a_4=1$ and $a_3=0$, so in fact, we have $a_{n+1}\le F_{2n-4}$, so $a_n\le F_{2n-6}$, so we're done.

Let $C_n=A_{2n}B_n$. Now $$\frac{C_{n+2}}{A_{2(n+2)}}=\frac{\left(\frac{C_{n+1}}{A_{2(n+1)}}\right)^3+1}{\frac{C_{n}}{A_{2n}}}$$Notice that $A_{2n+4}=\frac{A_{2n+2}^3}{A_{2n}}$. Hence the terms with $A$ cancelled. and we have $$C_{n+2}=\frac{C_{n+1}^3+A_{2n+2}^3}{C_n}\qquad (1)$$Now we have $$C_{n+1}=\frac{C_{n}^3+A_{2n}^3}{C_{n-1}}\qquad (2)$$and $$C_{n}=\frac{C_{n-1}^3+A_{2n-2}^3}{C_{n-2}}\qquad(3)$$Now assume $C_1,C_2,...,C_{n+1}$ are all integers. Then from $(2)$ $$C_{n+1}^3\equiv A_{2n}^9C_{n-1}^{-3}\pmod {C_n}$$From $(3)$, $C_{n-1}^3\equiv -A_{2n-2}^3\pmod{C_n}$ Hence $C_{n+1}^3+A_{2n+2}^3\equiv -A_{2n+2}^3+A_{2n+2}^3\equiv 0\pmod{C_n}$ This compeltes the proof.