such that![\[
4k^3 + 4k + 1
\]](http://latex.artofproblemsolving.com/f/3/5/f355e456cd47ecfdb13597d52fec3d848b67c594.png)
.
and 
of 
are said to be friends if the following conditions are true:
elements.[/quote]
be a circle on the plane. Let 
and 
be circles which are internally tangent to 
and 
respectively and let the intersection points of 
and 
.
.
and 
respectively. Let the second intersection point of the line 
and 
and let the second intersection point of the circumcircle of 
and 
be 
and let the intersection points of 
and 
be 
.
be a scalene triangle with incenter 
and incircle 
be 
respectively. Let the line 
intersect the circumcircle of 
.
lies between the points 
and 
.
be a circle that passes through 
and that is tangent to 
which lies on different semi-planes with 
with respect to the line 
at points 
.
and 
lies on the circumcircle of 
and 
lies on 
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 Fibonacci exponents.
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 
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 
.
Now we have
and
Now assume 
are all integers. Then from 
From 
,
)
.
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)
