Let $({{x}_{n}})$ be an integer sequence such that $0\le {{x}_{0}}<{{x}_{1}}\le 100$ and $${{x}_{n+2}}=7{{x}_{n+1}}-{{x}_{n}}+280,\text{ }\forall n\ge 0.$$a) Prove that if ${{x}_{0}}=2,{{x}_{1}}=3$ then for each positive integer $n,$ the sum of divisors of the following number is divisible by $24$ $${{x}_{n}}{{x}_{n+1}}+{{x}_{n+1}}{{x}_{n+2}}+{{x}_{n+2}}{{x}_{n+3}}+2018.$$b) Find all pairs of numbers $({{x}_{0}},{{x}_{1}})$ such that ${{x}_{n}}{{x}_{n+1}}+2019$ is a perfect square for infinitely many nonnegative integer numbers $n.$
Problem
Source: VMO 2019
Tags: Integer sequence, perfect number, sum of divisors
20.06.2019 15:47
Here is my solution for part a Solution We need a lemma Lemma: Let $n \in \mathbb{N^*}$ which satisfies $n + 1 \vdots 24$. Then: $\sigma(n) \vdots 24$ Back to the main problem Let $y_n = x_n x_{n + 1} + x_{n + 1} x_{n + 2} + x_{n + 2} x_{n + 3}, \forall n \in \mathbb{N}$ We have: $x_0 = 2$, $x_1 = 3$, $x_2 = 299 \equiv 2$ (mod $3$), $x_3 = 2370 \equiv 0$ (mod $3$) We also have: $x_{n + 2} = 7x_{n + 1} - x_n + 280 \equiv x_{n + 1} - x_n + 1$ (mod $3$) Then by induction, we have: $x_{2k} \equiv 0$ (mod $3$), $x_{2k + 1} \equiv 2$ (mod $3$) $(k \in \mathbb{N})$ But: $x_0 = 2$, $x_1 = 3$, $x_2 = 299 \equiv 3$ (mod $8$), $x_3 = 2370 \equiv 2$ (mod $8$) and $x_{n + 2} = 7x_{n + 1} - x_n + 280 \equiv 7x_{n + 1} - x_n$ (mod $8$) so by induction, we have: $x_{3k} \equiv 2$ (mod $8$), $x_{3k + 1} \equiv x_{3k + 2} \equiv 3$ (mod $8$) $(k \in \mathbb{N})$ Hence: $y_n \equiv 0$ (mod $3$), $y_n \equiv 5$ (mod $8$) or $y_n + 2018 \equiv 2018 \equiv 2$ (mod $3$), $y_n + 2018 \equiv 2023 \equiv 7$ (mod $8$) Then: $y_n + 2019 \vdots 24$ So by the lemma, $\sigma(y_n + 2018) \vdots 24$
11.04.2021 04:25
Does anyone have solution for part b?
15.06.2021 10:14
Part a) Lemma: If $n \in \mathbb{N}$ such that $24 \mid n + 1$, then the sum of its positive divisors $\sigma(n)$ is divisible by $24$. Proof: Note that if $24 \mid n + 1$, then $n \equiv 2 \pmod{3}$ and $n \equiv 7 \pmod{8}$. Thus, $n$ is not a perfect square. Then $\sigma(n) = \sum_{d \mid n, d^2 < n} \left(d + \frac{n}{d}\right) = \sum_{d \mid n, d^2 < n} \left(\frac{d^2 + n}{d}\right)$. Since $d^2 \equiv 1 \pmod{3}$ and $d^2 \equiv 1 \pmod{8}$ for all positive divisors $d$ of $n$, $d^2 + n \equiv 0 \pmod{24}$. Thus, $\sigma(n) \equiv 0 \pmod{24}$. Now we need to show that for all positive integers $n$, $(x_{n}x_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+2018) + 1 \equiv 0 \pmod{24} \iff x_{n}x_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3} \equiv -3 \pmod{24}$. If we take $(x_n) \pmod{8}$, then we get $2, 3, 3, 2, 3, 3, \ldots$, and for all $n$ we have $x_{n}x_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3} \equiv 2 \cdot 3 + 3 \cdot 3 + 3 \cdot 2 \equiv -3 \pmod{8}$. If we take $(x_n) \pmod{3}$, then we get $2, 0, 2, 0, 2, 0, \ldots$, and for all $n$ we have $x_{n}x_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3} \equiv 2 \cdot 0 + 0 \cdot 2 + 2 \cdot 0 \equiv 0 \pmod{3}$. Thus, $x_{n}x_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3} \equiv -3 \pmod{24}$ for all $n$. Part b) Lemma: $x_{n+1}^2- x_{n}x_{n+2} - 280x_{n+1} = C$ for some integer constant $C$. Proof: $x_{n+1}^2- x_{n}x_{n+2} - 280x_{n+1} = x_{n+1}(x_{n+1} - 280) - x_{n}(7x_{n+1} - x_n + 280)$ $= x_{n+1}(7x_{n} - x_{n-1}) - x_{n}(7x_{n+1} - x_{n} + 280) = x_{n}^2 - x_{n-1}x_{n+1} - 280x_{n}$ $= \ldots = x_1^2 - x_0x_2 - 280x_1 = C$. Now $x_{n+1}^2- x_{n}x_{n+2} - 280x_{n+1} = C$ $\iff x_{n+1}^2 - x_{n}(7x_{n+1} - x_n + 280) - 280x_{n+1} = C$ $\iff (x_{n+1} + x_{n} - 140)^2 = 9(x_{n+1}x_{n} + 2019) + C + 1429$. If $x_{n+1}x_{n} + 2019$ is a perfect square, then $x_{n+1} + x_{n} - 140 + 3\sqrt{x_{n+1}x_{n} + 2019} \mid C + 1429$. Notice that $(x_n)$ is an increasing unbounded sequence, so there exists an integer $m$ such that $x_{n+1} + x_{n} - 140 + 3\sqrt{x_{n+1}x_{n} + 2019} > C + 1429$ for all $n \geq m$. So if $x_{n+1}x_{n} + 2019$ is a perfect square for infinitely many $n$, $C + 1429 = 0 \iff (x_{n+1} + x_{n} - 140)^2 = 9(x_{n+1}x_{n} + 2019)$ for all $n$. Then $(x_1 + x_0 - 140)^2 \geq 2019 \cdot 9 > 134^2$, thus, $|x_0 + x_1 - 140| \geq 135$. Since $x_0 + x_1 - 140 < 59 < 135$, $x_0 + x_1 - 140 < 0$ and $140 - x_0 - x_1 \geq 135 \iff x_0 + x_1 \leq 5$. From $2x_0 < x_0 + x_1 \leq 5$, we get $x_0 = 0, 1, 2$. Remember that $C = x_1^2 - x_0x_2 - 280x_1 = x_1^2- x_0(7x_1 - x_0 + 280) - 280x_1 = x_0^2 + x_1^2- 7x_0x_1 - 280(x_0 + x_1) = -1429 \implies x_0^2 + x_1^2 \equiv 6 \pmod{7}$. If $x_0 = 0$, $x_1^2 \equiv 6 \pmod{7}$, which is impossible. If $x_0 = 1$, $x_1^2 \equiv 5 \pmod{7}$, which is impossible. If $x_0 = 2$, since $x_0 + x_1 \leq 5$ and $x_0 < x_1$, $x_1 = 3$. In this case, $C = x_0^2 + x_1^2 - 7x_0x_1 - 280(x_0 + x_1) = 4 + 9 - 42 - 280(5) = -1429$. Therefore, $(x_0, x_1) = \boxed{(2, 3)}$ is the only pair such that $x_{n}x_{n+1} + 2019$ is a perfect square for infinitely many $n$.