Two Recurrences

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#1 h Mar 22, 2015, 5:21 AM • 4 Y

Y by doxuanlong15052000, Davi-8191, Adventure10, Mango247

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.

This post has been edited 4 times. Last edited by rkm0959, Jun 6, 2015, 2:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#2 h Mar 22, 2015, 7:20 AM • 2 Y

Y by Adventure10, Mango247

Hints

This post has been edited 2 times. Last edited by rkm0959, Jun 6, 2015, 5:36 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#3 h Jun 6, 2015, 6:18 PM • 4 Y

Y by shinichiman, Exista, Adventure10, Mango247

Wrong Solution
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 post has been edited 4 times. Last edited by rkm0959, Mar 13, 2016, 10:24 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#4 h Jun 6, 2015, 6:47 PM • 4 Y

Y by VyasR, neverlose, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VyasR

21 posts

VyasR

#5 h Jun 6, 2015, 6:51 PM • 3 Y

Y by neverlose, Adventure10, Mango247

WOW! NICE LATEX!!!!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

polya78

105 posts

polya78

#6 h Jun 11, 2015, 8:18 PM • 3 Y

Y by toto1234567890, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shinichiman

3212 posts

shinichiman

#7 h Mar 13, 2016, 9:20 AM • 2 Y

Y by Adventure10, Mango247

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 \}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#8 h Mar 13, 2016, 10:23 AM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shinichiman

3212 posts

shinichiman

#9 h Mar 13, 2016, 10:46 AM • 4 Y

Y by rkm0959, Exista, Adventure10, Mango247

rkm0959 wrote:

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

Need time to check this

This post has been edited 5 times. Last edited by shinichiman, Feb 5, 2017, 12:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

freefrom_i

41 posts

freefrom_i

#10 h Oct 7, 2016, 1:55 PM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ScienceHouse

6 posts

ScienceHouse

#11 h Feb 5, 2017, 8:52 AM • 3 Y

Y by shinichiman, Adventure10, Mango247

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}$ .
Proof.

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

for63434

105 posts

for63434

#12 h Mar 19, 2017, 3:37 PM • 2 Y

Y by Adventure10, Mango247

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)

This post has been edited 1 time. Last edited by for63434, Mar 19, 2017, 3:42 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EagleEye

497 posts

EagleEye

#13 h Jul 7, 2020, 8:56 PM

Y by

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.

This post has been edited 4 times. Last edited by EagleEye, Jul 7, 2020, 8:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#14 h Jul 17, 2020, 1:54 AM

Y by

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.

This post has been edited 1 time. Last edited by yayups, Jul 17, 2020, 1:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathaddiction

308 posts

mathaddiction

#15 h Oct 7, 2020, 7:37 AM • 2 Y

Y by Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jaescl

11 posts

jaescl

#16 h Mar 1, 2025, 8:17 PM

Y by

Note that the sequence denoted by the letter $B$ shares the same recurrence relation as the sequence defined in the notes of Darij Grinberg (Page 126 and $r=3$ ) but with a different value for $B_2$ . Hence some results are also valid for the sequence of this thread, as for example:
$B_{n}=B_{n-4}B_{n-1}^{3}-\left(\frac{(B_{n-2}^{3}+1)^3-1}{B_{n-2}}\right)$ Which can be used to prove the claim of the first post of this thread or other statements such as the following:

The expressions $k^{F_{2n}}B_{n-2}B_{n+1}^{3}$ and $k^{F_{2n}}\left(\frac{(B_{n}^{3}+1)^3-1}{B_{n}}\right)$ leave the same remainder when divided by $k^{F_{2n}-F_{2(n-1)}}$ for every integer $n\geq 3$ (Where $F_{n}$ is the nth Fibonacci number)

See also: https://artofproblemsolving.com/community/c6h428645

This post has been edited 1 time. Last edited by jaescl, Mar 2, 2025, 5:48 PM
Reason: Link format issue

Z K Y