Number of sequences satisfying recurrence

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

Number of sequences satisfying recurrence

G H J

Reveal topic tags

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.

5 posts

#1 h Mar 24, 2025, 12:28 AM • 1 Y

Y by raghu7

Find the number of distinct positive integer sequences satisfying $x_1 = 1$ and $x_{n+1} = \frac{(x_{n}^2 + x_{n} +1)^{2025}}{x_{n-1}}$ for all $n > 1$

Z K Y

The post below has been deleted. Click to close.

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

3 posts

raghu7

#2 h Mar 24, 2025, 4:38 AM

Y by

Answer - There are $2026$ such sequences

Solution - First, consider $x_3=\frac{\left(x_2^2+x_2+1\right)^{2025}}{x_1}$ by substituting $n=2$ . Thus, $x_3=\left(x_2^2+x_2+1\right)^{2025}\Rightarrow x_3\equiv (0^2+0+1)^{2025}(\bmod{x_2})\Rightarrow \boxed{x_3\equiv 1(\bmod{x_2})}$ . Now,
$\begin{aligned} \text{for }n=3,\ x_4&=\frac{\left(x_3^2+x_3+1\right)^{2025}}{x_2}\in\mathbb{N}\\ \Rightarrow\left(x_3^2+x_3+1\right)^{2025}&\equiv 0(\bmod{x_2})\\ \Rightarrow\left(1^2+1+1\right)^{2025}&\equiv 0(\bmod{x_2})\\ \Rightarrow 3^{2025}&\equiv 0(\bmod{x_2})\\ \Rightarrow \Aboxed{x_2&=3^{k}}\text{ for some }k\in\{0,1,2,\ldots,2025\} \end{aligned}$
After fixing the value of $x_2=3^k$ , we can find an unique value of all the subsequent terms of the sequence. But we need to verify that all these values are positive integers. Let us assume that $x_{k-1}$ and $x_{k}$ are positive integers for some $k\geq 4$ . Then,
$\begin{aligned} x_{k-1}=\frac{\left(x_{k-2}^2+x_{k-2}+1\right)^{2025}}{x_{k-3}}&\text{ and }\ x_{k}=\frac{\left(x_{k-1}^2+x_{k-1}+1\right)^{2025}}{x_{k-2}}\\ \Rightarrow x_{k}&\equiv\left(0^2+0+1\right)^{2025}x^{-1}_{k-2}(\bmod{x_{k-1}})\\ \Rightarrow \Aboxed{x_k&\equiv x^{-1}_{k-2}(\bmod{x_{k-1}})}\\ \text{Note that }x_{k+1}&=\frac{\left(x_{k}^2+x_{k}+1\right)^{2025}}{x_{k-1}}\\ \Rightarrow\left(x_{k}^2+x_{k}+1\right)^{2025}&\equiv 0(\bmod{x_{k-1}})\text{ for }x_{k+1}\text{ to be a positive integer}\\ \Rightarrow\left(x_{k-2}^{-2}+x_{k-2}^{-1}+1\right)^{2025}&\equiv 0(\bmod{x_{k-1}})\\ \Rightarrow \left(x^{-1}_{k-2}\right)^{2025}\left(x_{k-2}^{2}+x_{k-2}^{1}+1\right)^{2025}&\equiv 0(\bmod{x_{k-1}})\\ \Rightarrow \left(x^{-1}_{k-2}\right)^{2025}x_{k-3}x_{k-1}&\equiv 0(\bmod{x_{k-1}})\\ \Rightarrow 0&\equiv 0(\bmod{x_{k-1}}) \end{aligned}$
Hence, we deduce that if $x_{k-1}$ and $x_{k}$ are positive integers for some $k\geq 4$ , then $x_{k+1}$ is also a positive integer. Now, we have $x_3=\left(x_2^2+x_2+1\right)^{2025}=\left(3^{2k}+3^k+1\right)^{2025}\in\mathbb{N}$ and $x_4=\frac{\left(x_3^2+x_3+1\right)^{2025}}{x_2}\in\mathbb{N}$ by divisibility. Hence, using mathematical induction with $x_3, x_4$ as the base case, we conclude that all the subsequent terms are positive integers. Therefore, the number of possible positive integer sequences $\left(x_n\right)_{n\in\mathbb{N}}$ is same as the number of possible values of $x_2$ which is $\boxed{2026}$ .

Z K Y

The post below has been deleted. Click to close.

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

29 posts

#3 h Monday at 12:40 PM • 1 Y

Y by User21837561

also posted here

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a