Assume that $a_1, a_2, a_3$ are three given positive integers consider the following sequence: $a_{n+1}=\text{lcm}[a_n, a_{n-1}]-\text{lcm}[a_{n-1}, a_{n-2}]$ for $n\ge 3$ Prove that there exist a positive integer $k$ such that $k\le a_3+4$ and $a_k\le 0$. ($[a, b]$ means the least positive integer such that$ a\mid[a,b], b\mid[a, b]$ also because $\text{lcm}[a, b]$ takes only nonzero integers this sequence is defined until we find a zero number in the sequence)
Problem
Source: iranian TST 2015 third exam day 1 P2
Tags: number theory, Iran, Iranian TST, least common multiple
12.06.2015 22:59
Attempting a TST problem... please find, if there are some flaws.. This proof is barely a sketch..
Attachments:



08.03.2018 15:46
We can see that $a_n \vdots a_{n-2} \forall n \geq 4$ so $[a_n,a_{n-1}] \vdots [a_{n-1},a_{n-2}] \forall n \geq 4 $. Put $g(n)=\frac{[a_{n+2},a_{n+1}]}{[a_{n+1},a_n]}$, $g(2) \leq a_3-1$. We have that $a_{n+1}=[a_n,a_{n-1}]\frac{g(n-2)-1}{g(n-2)}$ so $(g(n-2)-1)[a_n,a_{n-1}]$ is divisible both $a_{n+1},a_{n}$ then $(g(n-2)-1)[a_n,a_{n-1}] \geq [a_{n+1},a_n]$, so $g(n-2)-1 \geq g(n-1)$. So there exist $u\leq a_3+1$ such that $g(u)=1$. Then $a_{u+3}=0$ $Q.E.D$
28.05.2022 14:54
We will in fact prove the bound of $k \le a_3 + 3$ (and $a_k \le 0$). Let $$ b_n = \frac{a_n}{[a_{n-2},a_{n-3}]} \qquad \forall ~ n \ge 5 $$We directly have that $$ a_{n-2} \mid a_n \qquad \forall ~ n \ge 4 $$Which then also gives $a_n$ is divisible by $a_{n-3}$ for all $n \ge 5$. Hence $b_n$ is integral. Key Claim: $b_{n+1} < b_n ~~ \forall ~ n \ge 5$. Proof: Fix any $n \ge 5$. Then, \begin{align*} a_{n+1} &= [a_n,a_{n-1}] - [a_{n-1} - a_{n-2}] \\ &= [b_n \cdot [a_{n-2},a_{n-3}],a_{n-1}] - [a_{n-1} , a_{n-2}] \\ &= [b_n,a_{n-2},a_{n-3},a_{n-1}] - [a_{n-1} , a_{n-2} ] \\ &= [b_n,a_{n-2}a_{n-1}] - [a_{n-1},a_{n-2}] \qquad \qquad \qquad ( \because a_{n-3} \mid a_{n-1} ) \\ \implies b_{n+1} &= \frac{a_{n+1}}{ [a_{n-1},a_{n-2}] } < b_n \end{align*}Proving our Claim. $\square$ Now to complete the proof, it suffices to show that $b_5 \le a_3 - 2$, since if that happens then $b_k = 0$ for some $k \le a_3 + 3$, meaning $a_k = 0$. Observe, $$ a_4 = [a_3,a_2] - [a_2,a_1] = ca_2 $$for some $c \le a_3 -1$. Then, \begin{align*} a_5 = [a_4,a_3] - [a_3,a_2] = [ca_2,a_3] - [a_3,a_2] \\ \implies b_5 = \frac{a_5}{[a_3,a_2]} \le c-1 \le a_3 - 2 \end{align*}This completes the proof. $\blacksquare$ Remark: Equality can indeed be achieved: Take $a_1=1,a_2=2,a_3=3$. Then, \begin{align*} a_4 = [a_3,a_2] - [a_2,a_1] = [3,2] - [2,1] = 6 - 2 = 4 \\ a_5 = [a_4,a_3] - [a_3,a_2] = [4,3] - [3,2] = 12 - 6 = 6 \\ a_6 = [a_5,a_4] - [a_4,a_3] = [6,4] - [4,3] = 12 - 12 = 0 \end{align*}So $k=6 = a_3 + 3$ is the least number for which $a_k \le 0$.