One secuence satisfying condition

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

One secuence satisfying condition

G H J

Reveal topic tags

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

555 posts

#1 h Sep 4, 2011, 12:18 AM • 2 Y

Y by Adventure10, cubres

Prove that there exists only one infinite secuence of positive integers $a_1,a_2,...$ with $a_1=1$ , $a_2>1$ and $a_{n+1}^3 + 1 = a_na_{n+2}$ for all positive integers $n$ .

Z K Y

The post below has been deleted. Click to close.

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

138 posts

#2 h Sep 4, 2011, 4:19 AM • 3 Y

Y by Adventure10, Mango247, cubres

I have an (little) approach

Let's suppouse that $a_2=2$ then se sequence is $1, 2, 5, 13, 34...$ and the definition of this sequence is

$a_1=1$
$a_n=\displaystyle a_{n-1}+\sum_{i=1}^{n-1}a_i$

I could not prove that it is the sequence (neither that it is the only sequence) but at least it works.

Z K Y

The post below has been deleted. Click to close.

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

6555 posts

#3 h Sep 4, 2011, 7:27 PM • 5 Y

Y by Adventure10, Mango247, cubres, and 2 other users

ZetaSelberg, your sequence is wrong. Is it possible that you have misread 3rd power as 2nd power?

About the problem... First it is clear that $a_2$ can only be $2$ ; otherwise $a_4\notin\mathbb Z$ .

The interesting part is to prove that all members of the sequence are integers if $a_2=2$ . The sequence is A003818 in Sloane. Armed with this keyword, we get two topics:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=287631
http://www.artofproblemsolving.com/Forum/viewtopic.php?f=36&t=299591

No proof, though. Why not give one?

Theorem 1. Let $\left(b_1,b_2,b_3,...\right)$ be a sequence of positive rational numbers defined recursively by

$b_1=1$ , $b_2=2$ and $b_{n+1}=\frac{b_n^3+1}{b_{n-1}}$ for every integer $n\geq 2$ .

Then, $b_n$ is a positive integer for every positive integer $n$ .

Proof of Theorem 1. We are going to show that every integer $N\geq 3$ satisfies the following assertion:

(1) The numbers $b_1$ , $b_2$ , ..., $b_{N+1}$ are positive integers, and $b_{N-1}$ is coprime to $b_N$ .

In fact, we will prove (1) by induction over $N$ :

The induction base ( $N=3$ ) is very easy (just notice that the recurrent definition of $\left(b_1,b_2,b_3,...\right)$ yields $b_3=\frac{b_2^3+1}{b_1}=\frac{2^3+1}{1}=9$ and subsequently $b_4=\frac{b_3^3+1}{b_2}=\frac{9^3+1}{2}=365$ ).

Now for the induction step. Let $n\geq 3$ be an integer. Assume that (1) holds for $N=n$ . Now let us prove that (1) holds for $N=n+1$ .

Since (1) holds for $N=n$ , we know that the numbers $b_1$ , $b_2$ , ..., $b_{n+1}$ are positive integers, and that $b_{n-1}$ is coprime to $b_n$ .

Now, the recurrent definition of $\left(b_1,b_2,b_3,...\right)$ yields $b_{n+2}=\frac{b_{n+1}^3+1}{b_n}$ , $b_{n+1}=\frac{b_n^3+1}{b_{n-1}}$ and $b_n=\frac{b_{n-1}^3+1}{b_{n-2}}$ . Since $\frac{b_{n-1}^3+1}{b_{n-2}}=b_n$ , we have $b_{n-1}^3+1 = b_nb_{n-2}\equiv 0\mod b_n$ .

Since $b_{n-1}$ is coprime to $b_n$ , we see that $b_{n-1}^3$ is coprime to $b_n$ .

Substituting $b_{n+1}=\frac{b_n^3+1}{b_{n-1}}$ in $b_{n+2}=\frac{b_{n+1}^3+1}{b_n}$ , we obtain

(2) $b_{n+2}=\frac{\left(\frac{b_n^3+1}{b_{n-1}}\right)^3+1}{b_n}=\frac{\left(b_n^3+1\right)^3+b_{n-1}^3}{b_nb_{n-1}^3}$ .

Now, $b_n\equiv 0\mod b_n$ , so that $\left(b_n^3+1\right)^3+b_{n-1}^3\equiv \left(0^3+1\right)^3+b_{n-1}^3=1+b_{n-1}^3=b_{n-1}^3+1\equiv 0\mod b_n$ . In other words, $b_n\mid \left(b_n^3+1\right)^3+b_{n-1}^3$ . On the other hand, $\frac{b_n^3+1}{b_{n-1}}=b_{n+1}$ is an integer, so that $b_{n-1}\mid b_n^3+1$ and thus $b_{n-1}^3\mid \left(b_n^3+1\right)^3$ . Hence, $b_{n-1}^3\mid \left(b_n^3+1\right)^3+b_{n-1}^3$ as well (because clearly $b_{n-1}^3\mid b_{n-1}^3$ ). So we now know that the number $\left(b_n^3+1\right)^3+b_{n-1}^3$ is divisible by both of $b_{n-1}^3$ and $b_n$ . Since $b_{n-1}^3$ is coprime to $b_n$ , this yields that the number $\left(b_n^3+1\right)^3+b_{n-1}^3$ is also divisible by the product $b_nb_{n-1}^3$ . Hence, $\frac{\left(b_n^3+1\right)^3+b_{n-1}^3}{b_nb_{n-1}^3}$ is an integer. Due to (2), this shows that $b_{n+2}$ is an integer. Thus, $b_{n+2}$ is a positive integer (since clearly $b_{n+2}>0$ ). Combined with the fact that $b_1$ , $b_2$ , ..., $b_{n+1}$ are positive integers, this yields that $b_1$ , $b_2$ , ..., $b_{n+2}$ are positive integers.

Besides, $b_{n+1}=\frac{b_n^3+1}{b_{n-1}}$ , so that $b_{n-1}b_{n+1}=b_n^3+1$ and thus $1=b_{n-1}b_{n+1}-b_n^3$ . Hence, every common divisor of $b_n$ and $b_{n+1}$ must also divide $1$ . In other words, $b_n$ and $b_{n+1}$ are coprime. So we have shown that $b_n$ is coprime to $b_{n+1}$ .

We have thus shown that $b_1$ , $b_2$ , ..., $b_{n+2}$ are positive integers, and that $b_n$ is coprime to $b_{n+1}$ . In other words, (1) holds for $N=n+1$ . This completes the induction step.

Thus, by induction, (1) is proven for all $N\in\mathbb N$ . The claim of Theorem 1 now immediately follows.

Z K Y

The post below has been deleted. Click to close.

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

138 posts

#4 h Sep 4, 2011, 7:43 PM • 2 Y

Y by Adventure10, cubres

darij grinberg wrote:

ZetaSelberg, your sequence is wrong. Is it possible that you have misread 3rd power as 2nd power?

Yeess! Now I had to go an visit an optometrist because it is the third time I have this problem.

Thanks for the solution.

Z K Y

The post below has been deleted. Click to close.

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

11 posts

jaescl

#5 h Oct 13, 2011, 1:15 AM • 4 Y

Y by Adventure10, Mango247, cubres, and 1 other user

Considering the above sequence, prove or disprove whether the following expressions take integer values for every positive integer $n$ :

$\frac{b_{n}+b_{n+4}}{b_{n+2}}$
$\frac{b_{n}(b_{n+3}+1)}{b_{n+1}+1}$

I have no solution yet.

Z K Y

The post below has been deleted. Click to close.

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

6555 posts

#6 h Oct 13, 2011, 2:01 AM • 2 Y

Y by Adventure10, cubres

Very nice observations.

Theorem 2. Let $\left( b_{1},b_{2},b_{3},...\right)$ be the sequence of integers defined in Theorem 1 (in post #3 above).

(a) Every integer $n\geq3$ satisfies $b_{n}\mid b_{n-2}+b_{n+2}$ .

(b) Every integer $n\geq2$ satisfies $b_{n}+1\mid b_{n-1}\left( b_{n+2}+1\right)$ .

Proof of Theorem 2. From Theorem 1, we know that $b_{n}$ is a positive integer for every positive integer $n$ .

From the auxiliary result (1) that we proved during our proof of Theorem 1, we know that

(3) $b_{N-1}$ is coprime to $b_{N}$ for every integer $N\geq3$ .

(a) Let $n\geq3$ be an integer. From the auxiliary result (2) that we proved during our proof of Theorem 1, we know that

$b_{n+2}=\dfrac{\left( b_{n}^3+1\right) ^{3}+b_{n-1}^{3}}{b_{n}b_{n-1}^{3}}$ .

Thus,

$b_{n+2}b_{n}b_{n-1}^{3}=\left( b_{n}^3+1\right) ^{3}+b_{n-1}^{3}$ .

Since $\left( b_{n}^3+1\right) ^{3}\equiv1\mod b_{n}^{2}$ (this congruence even holds modulo $b_{n}^{3}$ ), this yields

$b_{n+2}b_{n}b_{n-1}^{3}\equiv1+b_{n-1}^{3}=b_{n-1}^{3}+1\mod b_{n}^{2}$ .

But the recurrent definition of $\left( b_{1},b_{2},b_{3},...\right)$ yields $b_{n}=\dfrac{b_{n-1}^{3}+1}{b_{n-2}}$ , so that $b_{n-1}^{3} +1=b_{n}b_{n-2}$ . Thus,

$b_{n+2}b_{n}b_{n-1}^{3}\equiv b_{n-1}^{3}+1=b_{n}b_{n-2}\mod b_{n}^{2}$ .

Now,

$\left( b_{n+2}+b_{n-2}\right) b_{n}b_{n-1}^{3}=\underbrace{b_{n+2}b_{n}b_{n-1}^{3}}_{\equiv b_{n}b_{n-2}\mod b_{n}^{2}} +b_{n-2}b_{n}b_{n-1}^{3}$

$\equiv b_{n}b_{n-2}+b_{n-2}b_{n}b_{n-1}^{3}=b_{n}b_{n-2}\underbrace{\left( b_{n-1}^{3}+1\right) }_{=b_{n}b_{n-2}}=b_{n}b_{n-2}b_{n}b_{n-2}=b_{n}^{2}b_{n-2}^{2}$

$\equiv 0\mod b_{n}^{2}$ .

In other words, $b_{n}^{2}\mid\left( b_{n+2}+b_{n-2}\right) b_{n}b_{n-1}^{3}$ . Cancelling one $b_{n}$ out of this divisibility, we get $b_{n}\mid\left( b_{n+2}+b_{n-2}\right) b_{n-1}^{3}$ . Since $b_{n-1}^{3}$ is coprime to $b_{n}$ (because (3) (applied to $N=n$ ) yields that $b_{n-1}$ is coprime to $b_{n}$ ), this yields that $b_{n}\mid b_{n+2}+b_{n-2} = b_{n-2}+b_{n+2}$ . This proves Theorem 2 (a).

(b) Let $n\geq2$ be an integer. The recurrent definition of $\left(b_{1},b_{2},b_{3},...\right)$ yields $b_{n+2}=\dfrac{b_{n+1}^{3}+1}{b_{n}}$ , so that $b_{n}b_{n+2}=b_{n+1}^{3}+1$ . The recurrent definition of $\left( b_{1},b_{2},b_{3},...\right)$ also yields $b_{n+1}=\dfrac{b_{n}^{3} +1}{b_{n-1}}$ , so that $b_{n+1}b_{n-1}=b_{n}^{3}+1 = \left(b_n+1\right)\left(b_n^2-b_n+1\right)\equiv0\mod b_{n}+1$ .

We have

$b_{n}b_{n-1}\left( b_{n+2}+1\right) =b_{n}b_{n-1}b_{n+2}+b_nb_{n-1} =b_{n-1}\underbrace{b_{n}b_{n+2}}_{=b_{n+1}^{3}+1}+\underbrace{b_{n}} _{\equiv-1\mod b_{n}+1}b_{n-1}$

$\equiv b_{n-1}\left( b_{n+1}^{3}+1\right) +\left( -1\right) b_{n-1}=b_{n-1}b_{n+1}^{3}+b_{n-1}-b_{n-1}=b_{n-1}b_{n+1}^{3}$

$=\underbrace{b_{n+1}b_{n-1}}_{\equiv0\mod b_{n}+1}b_{n+1}^{2} \equiv 0\mod b_{n}+1$ .

In other words, $b_{n}+1\mid b_{n}b_{n-1}\left( b_{n+2}+1\right)$ . Since $b_{n}+1$ is coprime to $b_{n}$ , this yields $b_{n}+1\mid b_{n-1}\left( b_{n+2}+1\right)$ . This proves Theorem 2 (b).

Some educated guessing was used in this proof... I am wondering how much of it could be automated.

Z K Y

The post below has been deleted. Click to close.

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

6555 posts

#7 h Jan 8, 2015, 3:51 PM • 5 Y

Y by Tintarn, Adventure10, Mango247, jaescl, cubres

I just revisited this thread as I was looking for a simple example on the Laurent phenomenon in cluster algebras, and it dawned upon me that both theorems in my posts can be generalized:

Theorem 3. Let $r$ be a positive integer. Let $\left(b_1,b_2,b_3,...\right)$ be a sequence of positive rational numbers defined recursively by

$b_1=1$ , $b_2=2$ and $b_{n+1}=\frac{b_n^r+1}{b_{n-1}}$ for every integer $n\geq 2$ .

(a) Then, $b_n$ is a positive integer for every positive integer $n$ .

(b) If $r \geq 2$ , then every integer $n\geq3$ satisfies $b_{n}\mid b_{n-2}+b_{n+2}$ .

(c) If $r$ is odd, then every integer $n\geq2$ satisfies $b_{n}+1\mid b_{n-1}\left( b_{n+2}+1\right)$ .

Proof of Theorem 3. (a) The proof of Theorem 3 (a) can be obtained by replacing every $3$ by $r$ in the proof of Theorem 1 (in post #3 above), and making one further change: The induction base (the case $N=3$ ) becomes a bit more difficult. Here is how the induction base must be proven now: It is clear that $b_1$ and $b_2$ are positive integers, and $b_3$ is an integer as well (since $b_3 = \frac{b_2^r+1}{b_1}$ and $b_1 = 1 \mid b_2^r+1$ ). Also, $b_1$ , $b_2$ , $b_3$ and $b_4$ are clearly positive. To prove that $b_4$ is an integer, we need to argue as follows: We have $b_3 = \frac{b_2^r+1}{b_1} = \frac{2^r+1}{1}$ (since $b_1 = 1$ and $b_2 = 2$ ), so that $b_3 = \frac{2^r+1}{1} = 2^r+1$ is odd, and thus $b_3^r$ is odd, so that $b_3^r+1$ is even, and thus $2 \mid b_3^r + 1$ . But $b_4 = \frac{b_3^r+1}{b_2} = \frac{b_3^r+1}{2}$ (since $b_2 = 2$ ) is an integer (since $2 \mid b_3^r + 1$ ). Now, in order to complete the induction base, we need to prove that $b_2$ is coprime to $b_3$ . This is clear because $b_2 = 2$ whereas $b_3$ is odd.

(b) Assume that $r \geq 2$ . The proof of Theorem 3 (b) can be obtained by replacing every $3$ by $r$ in the proof of Theorem 2 (a) (in post #6 above). The assumption $r \geq 2$ is used in the claim that $\left( b_{n}^r+1\right) ^r \equiv1\mod b_{n}^{2}$ .

(c) Assume that $r$ is odd. The proof of Theorem 3 (c) can be obtained by replacing every $3$ by $r$ in the proof of Theorem 2 (b) (in post #6 above), and replacing the equality $b_{n}^{3}+1 = \left(b_n+1\right)\left(b_n^2-b_n+1\right)$ by $b_{n}^r + 1 = \left(b_n+1\right)\left(b_n^{r-1}-b_n^{r-2}+b_n^{r-3}\pm ... +1\right)$ (this makes sense because $r$ is odd).

The proof of Theorem 3 is thus complete.

This all, of course, is related to cluster algebras: Our recurrence equation describes a cluster algebra of a two-vertex quiver with $r$ arrows from one vertex to the other. See §3.1.2 in Philipp Lampe's Cluster algebras notes. The Laurent phenomenon for cluster algebras can thus be used to prove Theorem 3 (a), although it should be applied with care: we need to extend our sequence $\left(b_1, b_2, b_3, ...\right)$ by an extra initial term $b_0 = 1$ (check that the recurrence is still satisfied) in order to ensure that "Laurent polynomials in the initial values" actually translates into "integers". See also §3.1 of Lee/Schiffler, Positivity for cluster algebras, arxiv:1306.2415v3 for combinatorial expressions for the general term of this sequence.

Z K Y

The post below has been deleted. Click to close.

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

11 posts

jaescl

#8 h Feb 16, 2025, 6:21 PM • 1 Y

Y by cubres

See also Notes on the combinatorial fundamentals of algebra (from page 126 onward)
Let $B_n$ and $k$ be as defined at https://artofproblemsolving.com/community/c6h1065491. I claim that the following expression is an integer for every integer $n\geq 3$ :
$k^{L_{2n-4}}\left(\frac{B_{n+2}+B_{n-2}}{B_{n}}\right)$ Where $L_{n}$ is the nth Lucas number

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

Z K Y

The post below has been deleted. Click to close.

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

11 posts

jaescl

#9 h Mar 17, 2025, 1:59 AM

Y by

Plugging $r=3$ into result ( $107$ ) of the Grinberg's notes, we get:

$\left(\frac{B_{n+2}+B_{n-2}}{B_{n}}\right) = B_{n-2}B_{n+2} - \left(\frac{(B_{n}^{3}+1)^3-1}{B_{n}^2}\right)$
Multiplying both sides of the equality by $k^{L_{2n-4}}$ and using the recurrence formula for $B_{n+2}$ gives:

$k^{L_{2n-4}}\left(\frac{B_{n+2}+B_{n-2}}{B_{n}}\right) = \frac{k^{L_{2n-4}}B_{n-2}(B_{n+1}^3+1)}{B_{n}} - \frac{k^{L_{2n-4}}}{B_{n}}\left(\frac{(B_{n}^{3}+1)^3-1}{B_{n}}\right)$
Remember that the main theorem of the linked thread states that $k^{F_{2(n-3)}}B_{n}$ is an integer, where $F_{n}$ is the nth Fibonacci number.

Note that $L_{2n-4}=F_{2(n-1)}-F_{2(n-3)}$ and $k^{F_{2(n-1)}}=\frac{k^{F_{2n}}}{k^{F_{2n}-F_{2(n-1)}}}$

The original statement is equivalent to prove that the following expression is divisible by $k^{F_{2n}-F_{2(n-1)}}$ :
$\frac{k^{F_{2n}}B_{n-2}(B_{n+1}^3+1)}{k^{F_{2(n-3)}}B_{n}} - \frac{k^{F_{2n}}}{k^{F_{2(n-3)}}B_{n}}\left(\frac{(B_{n}^{3}+1)^3-1}{B_{n}}\right)$ A previous step in the proof is to prove that the expressions involved in the subtraction are integers.
The main result follows from the fact that 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$ , and that $k^{F_{2(n-3)}}B_{n}$ is coprime with $k^{F_{2n}-F_{2(n-1)}}$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a