,
for all functions 
,
for all non-negative real numbers 
and 
.
and 
be sequences of real numbers for which 
and
for all positive integers 
for which 
for all 
)
and 
be two concentric circles. Let 
and 
be any two equilateral triangles inscribed in 
and 
are any two points on ![\[ P'A^2 + P'B^2 + P'C^2 = A'P^2 + B'P^2 + C'P^2. \]](http://latex.artofproblemsolving.com/2/a/7/2a73de753f0332329b743d494272d3fb85f60ef9.png)
Y by doxuanlong15052000, Davi-8191, Adventure10, Mango247
For a fixed positive integer 
, there are two sequences 
and 
.
They are defined inductively, by the following recurrences.
, 
, 
, 
, 
Prove that for all positive integers
, 
is an integer.
, there are two sequences 
and 
.They are defined inductively, by the following recurrences.
, 
, 
, 
, 
Prove that for all positive integers
, 
is an integer.This post has been edited 4 times. Last edited by rkm0959, Jun 6, 2015, 2:13 PM
be the Fibonacci Sequence, which satisfies 
,
,
and 
are relatively prime, we mean that they are relatively prime as polynomials.
and 
and 
.
and 
,
for all positive integers 
,
is given in the problem statement.
,
.
.
and 
,
as a fraction of polynomials.
,
and 
,
for all 
= 
.
and 
are relatively prime to k, we are done. 
for all n.
and 
by hand and use Claim 2 to check that the claim works for 
and 
.
is an integer.
are all integers for all 
,
is 
for all 
and the recurrence for 
are all integers.
to 
.
is an integer 
(Claim 5)
(Claim 3)
is an integer. We are done. 
.
then if 
,
,
,
.
is a kth root of 
,
,
,
.
divides 
.
with 
and it still satisfies the condition. We will have 
but 
with 
.
.
is possible.
then let 
be any prime divisor of 
,
.
so 
.
but we have 
so 
.
.
is an integer for the case 
.
then 
and 
.
so 
.
so 
.
and 
.
so from 
Now we need to prove 
.
and 
.
is also a recursion (with 
)
are all integers. We have 
so it suffices to prove 
.
We can see that 
from Claim 4 so if 
with 
then from above, we obtain 
.
,
.
for 
and assume that 
is a polynomial with integer coefficient for each 
then we have 
should be 
,
is at least 
.
,
is an integer
can be easily solved by dropping 
,
,
is odd, and 
.
Since 
for every non-negative integer ![$P, Q\in\mathbb{Z}[x]$](http://latex.artofproblemsolving.com/9/c/9/9c9fa139b881a8a545ca1f787ae86c453ceb94c8.png)
s.t. 
.
be the sequence of rational functions satisfying 
,
,![\[f_{n+2}=\frac{f_{n+1}^3+1}{f_n}.\]](http://latex.artofproblemsolving.com/8/9/5/895f65072d3fe50f343bdaee771f22ab114fe0c5.png)
We have the following key claim.
is actually a Laurent polynomial (i.e. a finite integer linear combination of 
where 
and 
share no non-monomial polynomial factor where 
are integer polynomials.
verified by hand.
,
.![\[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}.\]](http://latex.artofproblemsolving.com/6/0/b/60bb314a90ce6eb930616e0c89fe5d3a2631a6c7.png)
To show that this is a Laurent polynomial, it suffices to show that any polynomial factor of the numerator of 
that is an irreducible polynomial to some power divides the numerator of 
and 
don't share any factors (by the inductive hypothesis), it suffices to show that 
and 
are Laurent polynomials.![\[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},\]](http://latex.artofproblemsolving.com/0/a/c/0ac55f3b5025ede37511d1270ac3c153f7861959.png)
which is clearly a Laurent polynomial. Furthermore, ![\[P/f_{n-2}^3 = 1+f_n^3,\]](http://latex.artofproblemsolving.com/5/a/5/5a515a94b8a664f6b85100bca70222588db12f7f.png)
which is also clearly a Laurent polynomial. Thus, 
is a Laurent polynomial.
,![\[1=f_{n+1}f_{n-1}-f_n^3,\]](http://latex.artofproblemsolving.com/0/3/f/03f0ea366d2283412afb5dae656c047e0daeaba3.png)
so 
be the least non-negative integer such that 
is an integer polynomial. Then, ![\[a_{n+1}\le 3a_n-a_{n-1}.\]](http://latex.artofproblemsolving.com/5/9/b/59b9a6c346bd485b34ef4aa0669d3b55abaf3fc7.png)
![\[f_{n+1}f_{n-1}=f_n^3+1,\]](http://latex.artofproblemsolving.com/e/4/2/e42eeac0c7a95119711045011bb46bef8e65016c.png)
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.\]](http://latex.artofproblemsolving.com/e/a/f/eaf77733b85f0024c19258b8b313d8d1bef1004d.png)
Note that 
has nonzero constant term, so if 
is not a polynomial, then neither is 
,![\[a_{n+1}\le 3a_n-a_{n-1},\]](http://latex.artofproblemsolving.com/1/a/d/1ad6d9e684cc3e335a98497ebf78946dee712db4.png)
as desired. 
.![\[a_{n+1}\le F_{2k} a_{n-k+2} - F_{2k-2}a_{n-k+1}\]](http://latex.artofproblemsolving.com/e/5/2/e52ca4f0df20a3210edfc3d4833de9e9c5acbc96.png)
for all 
.
gives the desired result since 
and 
,
,
,
.
Notice that 
.
cancelled. and we have
Now we have
and
Now assume 
are all integers. Then from 
From 
,
shares the same recurrence relation as the sequence defined in the 
)
.
Which can be used to prove the claim of the first post of this thread or other statements such as the following:
and 
leave the same remainder when divided by 
for every integer 
(Where 
is the nth Fibonacci number)
