For a fixed positive integer $k$, there are two sequences $A_n$ and $B_n$. They are defined inductively, by the following recurrences. $A_1 = k$, $A_2 = k$, $A_{n+2} = A_{n}A_{n+1}$ $B_1 = 1$, $B_2 = k$, $B_{n+2} = \frac{B^3_{n+1}+1}{B_{n}}$ Prove that for all positive integers $n$, $A_{2n}B_{n+3}$ is an integer.
Problem
Source: 2015 Final Korean Mathematical Olympiad Day 2 Problem 5
Tags: number theory, Recurrence
06.06.2015 21:18
This was my solution at the contest, can you guys verify this? (My solution was more rigorous than this in the actual contest though)
06.06.2015 21:47
This took me an hour to write... Need to practice with LATEX more....
06.06.2015 21:51
WOW! NICE LATEX!!!!!
11.06.2015 23:18
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.
13.03.2016 11:20
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 \}$.
13.03.2016 12:23
Yep.. I realized that my proof was flawed very recently
13.03.2016 12:46
rkm0959 wrote: Yep.. I realized that my proof was flawed very recently
07.10.2016 16:55
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$
05.02.2017 11:52
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$.
19.03.2017 18:37
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)
07.07.2020 23:56
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.
17.07.2020 04:54
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.
07.10.2020 10:37
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.