Let $a_1,a_2,\cdots$ be an infinity sequence of positive integers such that $a_1=2021$ and $$a_{n+1}=(a_1+a_2+\cdots+a_n)^2-1$$for all positive integers $n$. Prove that for any integer $n\ge 2$, $a_n$ is the product of at least $2n$ (not necessarily distinct) primes.
Problem
Source: Thailand Online MO 2021 P3
Tags: Sequence, number theory
05.04.2021 07:15
Let $S_n$ be the sum of the first $n$ terms of the sequence. I'll prove the result by induction. In fact, I'll prove that $a_n$ is the product of at least $2n+3$ primes. For the base case, see that $a_2 = 2021^2 - 1 = (2020)(2022) = (2)(2)(5)(101)(2)(3)(337)$ which is $2(2) + 3 = 7$ primes. Now, assume the result holds until $n+1$ and we need to prove it for $n+2$ Observe that, $a_{n+1} = S_n^2 - 1$ and so $a_{n+2} = (a_{n+1} + S_n)^2 - 1$ $= (S_n^2 + S_n - 1)^2 - 1$ $= (S_n^2 + S_n)(S_n + S_n - 2)$ $= S_n(S_n+1)(S_n - 1)(S_n+2)$ $= a_{n+1}(S_n)(S_n+2)$ Since $a_{n+1}$ can be written as the product of $2n+5$ primes by the induction hypothesis, $a_{n+1}$ can be written as the product of $2n+5 + 2 = 2n+7 = 2(n+2) + 3$ primes, as required
05.04.2021 07:17
Here’s my solution: Let $S_n=a_1+a_2+\dots+a_n$, then $a_{n+1}=S_n^2-1$ Claim: $a_{n+2}=a_{n+1}(S_n)(S_n+2)$ Proof: Notice that \begin{align*}a_{n+2} &=S_{n+1}^2-1 \\ &=(S_{n+1}-1)(S_{n+1}+1)\\ &=(S_n+a_{n+1}-1)(S_n+a_{n+1}+1)\\ &=(S_n^2+S_n-2)(S_n^2+S_n)\\ &=(S_n^2-1)(S_n)(S_n+2)\\ &=a_{n+1}(S_n)(S_n+2), \end{align*}as desired. Then for $n\geq2$, if $a_n$ is the product of at least $2n$ primes, then $a_{n+1}$ is the product of at least $2n+2$ primes, therefore it suffices to prove the case when $n=2$ which we have $a_2={2021}^2-1=(2020)(2022)=2^3\times3\times5\times101\times337$ and so the problem is solved.
05.04.2021 07:18
Note: Just for your infomation, this is from Thailand Online Mathematical Olymiad, which is a mock competition but not the official National Olympiad. If you would, just so that it doesn't cause any misunderstanding, please include in the source that this is a mock contest.
05.09.2021 12:52
Let $S_{k}$ denote the sum of the first $k$ terms. We have that $a_{n}=S_{n-1}^2-1$, Now we get $a_{n+1}=a_{n}.S_{n-1}.(S_{n-1}+2)$ And the result follows by induction as $2021=43*47$.
05.09.2021 19:24
I mean this is algebra. Note that \begin{align*} a_{n+1}&=(a_1+\ldots+a_{n-1}+(a_1+\ldots+a_{n-1})^2-1)^2-1\\&=(a_1+\ldots+a_{n-1})(a_1+\ldots+a_{n-1}-1)(a_1+\ldots+a_{n-1}+1)(a_1+\ldots+a_{n-1}+2) \\&=a_n\cdot (a_1+\ldots+a_{n-1})\cdot (a_1+\ldots+a_{n-1}+2). \end{align*}As $a_2=2021^2-1=2^3\cdot 3\cdot 5\cdot 101\cdot 337$, we get that by induction that if $a_n$ is the product of at least $2n$ primes, then $a_{n+1}$ is the product of at least $2(n+1)$ primes.
09.02.2022 08:50
Jjesus wrote: Let $a_1,a_2,\cdots$ be an infinity sequence of positive integers such that $a_1=2021$ and $$a_{n+1}=(a_1+a_2+\cdots+a_n)^2-1$$for all positive integers $n$. Prove that for any integer $n\ge 2$, $a_n$ is the product of at least $2n$ (not necessarily distinct) primes. $$x_n = a_1+a_2+\cdots+a_n -1 \implies a_n =x_n - x_{n-1}$$$$x_{n +1}- x_n = x_n \cdot (x_n + 2)$$$$x_{n+1}=x_n(x_n+3)$$It suffices to prove that $x_n - x_{n-1}$ has at least $2n$ prime divisors. We prove this by induction. $$x_{n+1} - x_n = x_n(x_n+3) - x_{n-1}(x_{n-1}+3) = (x_n - x_{n-1})(x_n+x_{n-1} + 3) = (x_n - x_{n-1})(x_{n-1}+1)(x_{n-1}+3)$$$\blacksquare$