Define an index $i$ to be a peak if $a_i \ge a_{i+1}$. Note that if $i$ is not a peak then $(a_{i+1}, b_{i+1}) = (a_i+1, b_i-1)$. We claim that if $i$ and $k$ are adjacent peaks then $a_i \ge a_k$. Assume not. Set $(a_i, b_i) = (dx, dy)$ where $\gcd(x,y) = 1$. Then $(a_{i+1}, b_{i+1}) = (d+1, dxy-1)$. By assumption, we then arrive at the pair $(a_j, b_j) = (dx, dxy+d-dx)$ later, where $j < k$. At this point the GCD of these two numbers is $d < dx$, so $j$ must be a peak, contradiction. Thus, the peaks are monotonic, and eventually stabilize; moreover the sequence is bounded. Let $M = (\max a_i)!$. Now, note that $(a_i, b_i \mod M)$ determines $(a_{i+1}, b_{i+1} \mod M)$ since $\gcd(a_i, b_i)$ is determined by $b_i \mod M$, and also \[ b_{i+1} = \underbrace{\frac{a_i}{\gcd(a_i, b_i)}}_{\in \mathbb Z} b_i + 1. \]Since the number of such pairs is finite, $a_i$ is eventually periodic.

va2010 wrote: Suppose that $a_0, a_1, \cdots $ and $b_0, b_1, \cdots$ are two sequences of positive integers such that $a_0, b_0 \ge 2$ and \[ a_{n+1} = \gcd{(a_n, b_n)} + 1, b_{n+1} = \operatorname{lcm}{(a_n, b_n)} + 1 \]Show that the sequence $a_n$ is eventually periodic; in other words, there exist integers $N \ge 0$ and $t > 0$ such that $a_{n+t} = a_t$ for all $n \ge N$, The problem statement is wrong: The $b_n$ sequence is defined as $b_{n+1} = \text{lcm}(a_n, b_n) - 1$. The clarification for "eventually periodic" should have $a_{n + t} = a_n$.

It is obvious that $a_i\ge 2$ for all $i$, since $a_i= \gcd(a_{i-1}, b_{i-1})+1\ge 1+1=2$. Notice that if $a_n\mid b_n$ for some $n$, then $\gcd(a_n,b_n)=a_n$ and $\text{lcm}(a_n,b_n)=b_n$. So $a_{n+1}=a_n+1$, and $b_{n+1}=b_n-1$. Now, for any $n$, let $m$ be the maximal $m$ such that $a_{n+i}\mid b_{n+i}$ for all $i=0,1,\cdots m-1$ and $a_{n+m}\nmid b_{n+m}$. Then we have $a_{n+i}=a_n+i$ and $b_{n+i}=b_n-i$ for all $0\le i\le m$. Clearly such maximal $m$ must exist, otherwise $b_{n+i}=b_n-i<0$ for $i>b_n$, false since $b_{n+i}$ cannot be negative. Notice that by the choice of $m$, $a_{n+m}\nmid b_{n+m}$, then $$\gcd(a_{n+m},b_{n+m})\le \frac{a_{n+m}}{2}\le a_{n+m}-1$$so $a_{n+m+1}\le a_{n+m}$. Now, take any $n$ such that $a_{n-1}\neq a_n-1$, and consider the subsequence $a_n, a_{n+1},\cdots, a_{n+m}$, where $m$ is as define as above. We call it a \emph{segment}, denoted as $[a_n, a_{n+m}]$. Clearly from the definition of $m$, any segment is a finite sequence of consecutive positive integers. So we can partition the whole sequence $\{a_i\}^{\infty}_{i=0}$ into infinitely many segments, and every element belongs to a segment. Given a segment $[a_n, a_{n+m}]$, we would also like to denote $a_n$ to be the \emph{head} of the segment, and $a_{n+m}$ to be the \emph{tail} of the segment. Lemma 1. The tail of the segments are non-increasing, thus eventually constant. Proof. Suppose $[a_{i-p}, a_i]$, $[a_{i+1}, a_{i+q}]$ are two consecutive segments, we claim that $ a_i\ge a_{i+q}$. If $q=1$, then the result is immediate since $a_{i+1}\le a_i$, so suppose $q\ge 2$. Now suppose that $a_{i+q}>a_i$, then since $a_{i+1}\le a_i$, one of the consecutive numbers $a_{i+1}, a_{i+2}, \cdots, a_{i+q-1}$ is equal to $a_i$, suppose $a_{i+k}=a_i$ for some $1\le k \le q-1$. We have $a_{i+k}\mid b_{i+k}$ and $a_i\nmid b_i$ by definition, and so we have $$a_i=a_{i+k}\mid a_{i+k}+b_{i+k}=a_{i+1}+(k-1)+b_{i+1}-(k-1)=a_{i+1}+b_{i+1}=\gcd(a_i,b_i)+\text{lcm}(a_i,b_i)$$Clearly $a_i\mid \text{lcm}(a_i,b_i)$, so $a_i\mid\gcd(a_i, b_i) \Rightarrow a_i=\gcd(a_i,b_i) \Rightarrow a_i\mid b_i$, which contradicts the choice of $a_i$. So we must have $a_i\ge a_{i+q}$, which proves Lemma 1. So by Lemma 1, the tail of the segments are eventually constant. So suppose at some point, the tail of all subsequent segments is $\gamma$. So we have consecutive segments $[a_{s+1}, a_t], [a_{t+1}, a_u]$, where $\gamma=a_t=a_u$. It suffices to show that the head of all subsequent segments are constant after segment $[a_{t+1}, a_u]$ onwards. Lemma 2. We have $a_{u+1}=a_{t+1}=\alpha$ for some $\alpha\le \gamma$. Proof. It suffices to prove that $$a_{u+1}-1=\gcd(\gamma, b_u)=\gcd(\gamma, b_t)=a_{t+1}-1$$We have $$\gcd(\gamma, b_u)=\gcd(\gamma, a_u+b_u)=\gcd(\gamma, a_{t+1}+b_{t+1})=\gcd(\gamma,\gcd(\gamma, b_t)+\text{lcm}(\gamma, b_t))$$But since $\gcd(\gamma, b_t)\mid \gamma$ and $\gamma \mid \text{lcm}(\gamma, b_t)$, so we can write $\text{lcm}(\gamma, b_t)=k\cdot \gamma$, then $$\gcd(\gamma,\gcd(\gamma, b_t)+\text{lcm}(\gamma, b_t))=\gcd(\gamma, \gcd(\gamma, b_t)+ k \cdot \gamma)=gcd(\gamma,\gcd(\gamma, b_t))=\gcd(\gamma, b_t) $$This proves Lemma 2. So by Lemma 2, we have the consecutive segments $[a_{t+1}, a_u]=[\alpha, \gamma]$ and $[a_{u+1}, a_v]=[\alpha, a_v]$ for some $v$. But by Lemma 1 again, $a_v=\gamma$, since all tail of the segments from segment $[a_{s+1}, a_t]$ onwards is $\gamma$. So $[a_{u+1}, a_v]=[\alpha, \gamma]$. Continuing this manner, the head and tail of all subsequent segments are all equal to $\alpha$ and $\gamma$ respectively. So the sequence $\{a_i\}^{\infty}_{i=0}$ is eventually periodic, repeating the segment $[\alpha, \gamma]$, as we want to prove.

Note that each $a_i > 1$. Note that $a_{i+1} > a_i$ iff $a_i | b_i$, in which case, $a_{i+1} = a_i + 1, b_{i+1} = b_i - 1$. We claim that $a_{i+1} \leq a_i$ infinitely often. Indeed, if $a_i$ were to strictly increase after some point, then $b_i$ would strictly decrease, meaning $b_i$ eventually reaches $1$, in which case the next value of $a_i$ will be $2$, which can't be greater than the previous value of $a_i$. Define $k_i$ to be the $i^{th}$ index of no increase, such that $k_i$ is the $i^{th}$ smallest non-negative integer such that $a_{k_i} \geq a_{k_i + 1}$. Define the sequence $c_i$ by $c_i = a_{k_i}$. We claim that the sequence $c_i$ is non-increasing. Indeed, suppose $c_j < c_{j+1}$. Note that $b_{i+1} \equiv -1 mod a_i$. If $c_j < c_{j+1}$, we get that $x \equiv 0 mod a_{k_j}$, where $-(a_{k_j}-1) \leq x \leq -1$, a contradiction. Thus, $a_i$ is bounded. Let $m$ be the maximum value $a_i$ achieves. Then, define the state of the sequence $a_i$ by the current value of $a_i$, and the current values of $b_i$ modulo the integers $2$ to $m$. Note that the current state of $a_i$ uniquely determines all future states. As the number of possible states is finite, a state is eventually repeated, which causes the sequence to eventually be periodic.

Ayy, nice problem... very heavily based on observation- here's the sketch of my proof: Playing around with random sequences, we get if $a_n$ goes below a certain value (namely 6), it immediately ends our proof simply by casework for $a_n=2,3,4,5$ and on $b_n$- now all we have to do is prove that there'll be some value $a_i$ at which $a_i$ dips below $a_0$, and then finish off the problem with straightforward strong induction. The proof for why $a_0$ must always dip below $a_i$ isn't too hard either- firstly the only time when $a_1$ won't dip below $a_0$ is when $b=ka_0$- all's left is to take cases for $k$, thus proving that there exists some $a_n$ dipping below $a_0$, and we're done by strong induction.

Note that the sequence $a_i$ strictly decreases at each step unless $gcd(a_n, b_n) = a_n$ in which case $a_{n+1} = a_n + 1$. Also note that whenever the sequence $a_i$ decreases down to $2$, the problem becomes casework (and I'm too lazy to show this ) It suffices to prove that given $a_0$ and $b_0 = ka_0$, we obtain a sequence that becomes periodic. This is simple since $(a_0, ka_0) \to (a_0 +1, ka_0 -1)$. If $(a_0 + 1, ka_0 -1) \to (a_0 + 2, ka_0 -2)$, it is clear the next $a_i$ must decrease. In the other case, $(a_0 + 1, ka_0 -1)$ decreases in the $a$ coordinate. In either case, we have that the sequence will decrease, which finishes the problem.

It is not hard to see that if $a_j<a_{j+1},$ then $a_{j+1} = a_j+1$ and $a_j \mid b_j.$ Call $a_j$ a highboi if $a_j\ge a_{j+1}$. Consider the subsequence $S$ consisting of highbois. Claim: $S$ is monotonically decreasing. Proof. Assume the contrary. Let $a_j, a_k$ be adjacent highbois with $j<k$ such that $a_j<a_k.$ Let $a_p$ denote the term such that $a_p = a_j$ and $p<k.$ Observe then that $a_p\mid b_p.$ Let $d$ denote the gcd of $a_j, b_j.$ Observe that $a_{j+1}= d+1.$ Hence, $$b_p = (\tfrac{a_jb_j}{d}-1) - (a_j+b_j-(d+1)) + b_j = \tfrac{(a_j-d)(b_j-d)}{d}+b_j \equiv d\not\equiv 0 \pmod {a_p},$$implying $a_p\nmid b_p,$ contradiction. $\blacksquare$ It is obvious that $a_0, a_1,\dots $ and $b_0, b_1 \dots$ are infinite, giving that there exists $m$ such that for all $a_m, a_n\in S$ with $n>m, a_n = a_m.$ Moreover, observe from the above argument that $\gcd(a_n, b_n) = \gcd(a_m, b_m)$ as well, implying $a_{n+1}= a_{m+1}.$ Hence, this is enough to conclude that $a_0, a_1, \dots$ is indeed eventually periodic.

This problem is very rigid. Analyzing small cases helps a lot here. We call $a_n$ libertarian if $a_{n+1} \leq a_n$. Claim: If $a_i,a_j$ are two consecutive libertarian terms, with $i \leq j$ then $a_j \leq a_i$. Proof: Suppose that we have two consecutive libertarian terms $a_i,a_j$, with $i \leq j$ and $a_j > a_i$. Observe that the non-libertarian terms $a_n$ must satisfy $a_{n+1}=a_n+1$, and this can only occur if $a_n|b_n$. Then, since $a_{i+1},a_{i+2},...,a_{j-1}$ are non-libertarian, $a_k=a_{i+1}+(k-1)$ and $b_k=b_{i+1}-(k-1)$ for all $k=i+1,i+2,...,j-1$. Hence, since $a_j > a_i$ and the terms increase in exactly one each time, when $a_i$ appears again on the sequence, it will be non-libertarian. $$\implies a_n|b_{n+(a_n-a_{n+1})}=b_{n+1}-(a_n-a_{n+1}-1)=b_{n+1}+1+a_n-a_{n+1}$$$\implies a_n|a_{n+1}$, because $b_{n+1}+1=\operatorname{lcm}{(a_n,b_n)}$, which is divisible by $a_n$. But since $a_n$ is libertarian, we cannot have $a_n|a_{n+1}$. This proves the claim. $\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \square$ From the claim, we have that the libertarian terms of the sequence are eventually constant. Thus, there exists $N$ such that for all libertarian terms greater than $N$ are all equal. Since between two libertarian terms the sequence increases one-by-one, the sequence is eventually periodic, as desired. $\blacksquare$

Call a term $a_i$ bad if $a_i$ does not divide $b_i$. Note that if $a_i$ is not bad, then $a_{i+1} = a_i+1 ~,~ b_{i+1}=b_i - 1$. Of course, in any sequence, there is at least one bad term (otherwise, the sequence $b_i$ would become small and will even become negative, which is not possible). Now, consider the following statement $P(n)$ for any positive integer $n$ greater than $1$. $P(n) :-$ for some $i$, if $a_i=n$ is bad, then the sequence $a_0,a_1,\dots$ will eventually become periodic. Note that to complete the proof of this problem, it suffices to show $P(n)$ is true for all $n$. We will establish this using strong induction on $n$. Base case $P(2)$ is trivially true as if $a_i = 2$ is bad for some $i$, then $2=a_i=a_{i+1}=a_{i+2}=\cdots$. Now, for the induction step, suppose that $P(2),P(3),\dots,P(k-1)$ are true ($k \ge 3$). To prove $P(k)$ is also true. Assume that for some $i$, $a_i = k$ is bad. Note that if this sequence $a_0,a_1,\dots$ contains terms which are less than $k$ and also bad, then we would be done by our induction hypothesis. So we now assume that all bad terms of the sequence $a_0,a_1,\dots$ are greater than or equal to $k$. Now, write $a_i = dx ~,~ b_i=dy$ where $\gcd(x,y)=1$ and $x \ne 1$. Rest is easy from here (the sequence will become:- $d+1,\dots,dx ; d+1,\dots,dx ; \dots$).

Firstly, notice that $$a_{n+1}=(a_n,b_n)+1\leq a_n+1\hspace{20pt}(1)$$with equality holds if and only if $a_n|b_n$ We call a number $n$ good if $a_n>a_{n+1}$. Suppose $n_1<n_2<...$ are all good numbers. The crucial claim is Claim. $a_{n_i}\geq a_{n_{i+1}}$ Proof. Indeed, let $n_i=m$, let $d=(a_m,b_m)$ and $a_m=da$, $b_m=db$. Then $a>1$ and $$a_{m+1}=d+1\text{ and }b_{m+1}=dab-1$$Suppose on the contrary that $a_{n_{i+1}}>a_{n_i}$ then by $(1)$, $a_{m+1+da-d-1}=da$, so letting $k=m+1+da-d-1$ we have $a_k|b_k$ which implies $$da|dab-1-(da-d-1)$$Hence $da|d$, contradiction. $\blacksquare$ Now from the Claim we easily conclude that $a_{n}$ is bounded and the sequence $\{a_{n_i}\}$ is eventually constant, say equal to $c$. Then for sufficiently large term the sequence is bounded above by $c$. Let $k=[1,2,...,c]$ then by pigeonhole principle there exists $i,j$ such that $b_{n_i}\equiv b_{n_j}\pmod k$. It is easy to see that $a_k=a_{j-i+k}$ so we are done.

Nice problem! Note that $a_{n+1} \le a_n + 1$ and so increases by at most $1$ each time. Also, it increases by $1$ only if $a_n | b_n$ First, I'll show that $a_i$ is bounded, which will obviously finish since the sequence is determined by its previous terms and so $a_i$ will have to become periodic. Now, lets pretend its unbounded, then it has to increase by $1$ arbitrarily large number of times, which I'll show is not possible. Suppose at some point, the $(a_i, b_i) = (r,n)$ and the sequence increases after this, so suppose it goes $(r,n) \rightarrow (r+1, n-1) \rightarrow (r+2, n-2) \cdots \rightarrow (k,n+r-k)$ before falling again. Note that the sequence increases only if $r+q | n-q \iff r+q | n+r$, so $k$ must be the first number $> r$ such that $k \nmid n+r$, let $k = yz$ where $z | n+r$ but gcd$(y,n+r) = 1$, obviously we must have $y > 1$ Then, from $(yz, n+r-yz)$, it goes to $(z+1, ny + ry - y^2z - 1)$. Now, the new sum of $a_i + b_i$ is $ny + ry - y^2z + z$, but now see that $y$ does not divide this sum and so neither does $yz$. So, this time, the sequence cannot increase past $yz$ again. So, beyond this point, $a_i$ is bounded above by $yz$. Since there were only finitely many terms before this, the whole sequence is itself bounded, as desired. $\blacksquare$

I think this is different. We'll use the "peak" notation used in #2. Define an index $i$ to be a peak if $a_i \ge a_{i+1}$. Note that if $i$ is not a peak then $(a_{i+1}, b_{i+1}) = (a_i+1, b_i-1)$. Define $GCD(a,b) = G(a,b)$ and $LCM(a,b) = L(a,b)$. Solution. Claim. 1 Given the sequence $$(p,a)\rightarrow (p-c,b+c)\rightarrow \dots \rightarrow (p-1,b+1) \rightarrow (p,b)\rightarrow (X,Y)$$where $(p,a)$ is peak, then $X = p-c$. (a corollary of this is that $(p,b)$ is peak. This will be used in proving the next claim). Proof. By definition, $$p-c = G(p,a)+1 (*)$$$$b+c=L(p,a)-1(**)$$Note that $X = p-c \iff G(p,a)+1 = G(p,b)+1 \iff G(p,a)=G(p,b)$. a. Claim 2a. $G(p,a)|G(p,b)$ Proof. Let $x = G(p,a)$. Then $x|p,a$. From (*), $x|c+1$. From (**), since $x|c+1$ we have $x | b$. Thus $x | G(p,b)$. $\blacksquare$ b. Claim 2b. $G(p,b)|G(p,a)$ Proof. Let $x=G(p,b)$. Then $x|p,b$. From (**), $x|c+1$. From (*), since $x|c+1$ we have $x|G(p,a)$. $\blacksquare$. Thus $G(p,a)=G(p,b)$. $\blacksquare$ Claim 2. The subsequence of the peaks is non-increasing. Proof. Say we have the sequence $$(p,a) \rightarrow (q-c,b+c)\rightarrow \dots \rightarrow (q,b)$$where $(p,a)$ and $(q,b)$ are peaks, and there are no peaks between $(p,a)$ and $(q,b)$. If $p\ge q$, we are done. Otherwise $q>p$, and by Claim 1., there is a peak between $(p,a)$ and $(q,b)$ contradicting the minimality. $\blacksquare$.

v_Enhance wrote: Define an index $i$ to be a peak if $a_i \ge a_{i+1}$. Note that if $i$ is not a peak then $(a_{i+1}, b_{i+1}) = (a_i+1, b_i-1)$. We claim that if $i$ and $k$ are adjacent peaks then $a_i \ge a_k$. Assume not. Set $(a_i, b_i) = (dx, dy)$ where $\gcd(x,y) = 1$. Then $(a_{i+1}, b_{i+1}) = (d+1, dxy-1)$. By assumption, we then arrive at the pair $(a_j, b_j) = (dx, dxy-d-dx)$ later, where $j < k$. At this point the GCD of these two numbers is $d < dx$, so $j$ must be a peak, contradiction. Thus, the peaks are monotonic, and eventually stabilize; moreover the sequence is bounded. Let $M = (\max a_i)!$. Now, note that $(a_i, b_i \mod M)$ determines $(a_{i+1}, b_{i+1} \mod M)$ since $\gcd(a_i, b_i)$ is determined by $b_i \mod M$, and also \[ b_{i+1} = \underbrace{\frac{a_i}{\gcd(a_i, b_i)}}_{\in \mathbb Z} b_i + 1. \]Since the number of such pairs is finite, $a_i$ is eventually periodic. A little typo, it should be $dxy+d-dx$.

Hard, but lot of standard ideas. The main idea is that since $a_{n+1}-1\mid a_n$, either $a_{n+1}=a_n+1$, or $a_{n+1}=d+1$ for some divisor $d$ of $a_n$. So the sequence increases $a_i\to a_{i+1}$ if and only if $a_i\mid b_i$, and it will increase by $1$. The sequence is hence ``determined'' by the steps when it does not increase. To this end, define $i$ to be a peak if $a_i\nmid b_i$, i.e. $a_i \ge a_{i+1}$. Note that at least one non-peak exists since else the sequence is always decreasing, or constant. Claim: The $a$-values of the peaks form a non-increasing sequence. Proof: Suppose $n$ is a non-peak. Let $n+m$ be the minimal peak greater than $n$. Then $a_{n'}\mid b_{n'}$ for each $n'=n,n+1,\ldots,n+m-1$, so $a_{n'+1}=a_{n'}+1$ and $b_{n'+1}=b_{n'}-1$. Let $b_n=ka_n$. So \begin{align*} (a_n,b_n) &= (a_n, ka_n) \\ (a_{n+1},b_{n+1})&=(a_n+1, ka_n-1) \\ (a_{n+2},b_{n+2})&=(a_n+2, ka_n-2) \\ &\vdots \\ (a_{n+m},b_{n+m}) &= (a_n+m, ka_n-m). \end{align*}Let $d=\gcd(a_n+m,ka_n-m)$, so $a_{n+m+1}=d+1$ and $b_{n+m+1}=\frac{(a_n+m)(ka_n-m)}{d}-1$. Since $n+m$ is a peak, $a_n+m\nmid ka_n-m$, so $d<a_n+m$. Suppose FTSOC that the subsequent peak after $n+m$ has $a$-value greater than $a_n+m$. Then \begin{align*} (a_{n+m+1},b_{n+m+1}) &= \left( d+1, \frac{(a_n+m)(ka_n-m)}{d}-1\right) \\ &\vdots \\ (a_{x}, b_{x}) &= \left(a_n+m, \frac{(a_n+m)(ka_n-m)}{d}-(a_n+m-d) \right) \end{align*}for some $x$. Since we assumed $x$ is not a peak, $a_x\mid b_x$. So \[ a_n+m\mid \frac{(a_n+m)(ka_n-m)}{d}-(a_n+m-d) \implies a_n+m\mid d \]since $d\mid ka_n-m$. Combining the above with $d\mid a_n+m$, we have $d=a_n+m$. This contradicts $d<a_n+m$. $\blacksquare$ The key is to note that $\gcd(a_n,b_n)=\gcd(a_n,b_n+N)$, where $N=(a_m)!$, where $a_m=\max(a_i)$, which exists since the $a$-sequence is bounded. Also, $b_{n+1}=\frac{a_n}{a_{n+1}-1}b_n-1$, so $b_{n+1}\mod N$ can be determined from $a_n,a_{n+1}$, and $b_n\mod N$. Hence, $(a_{n+1},b_{n+1} \mod N)$ is determined by $(a_n, b_n\mod N)$. Since there are finitely many possibilities for $a_i$ and for $b_i\mod N$, the $a$-sequence is eventually periodic by Pigeonhole.

Rename $a_n$ with $f(n)$ and $b_n$ with $g(n)$, and let $f(n)+g(n) = s(n)$. Problem becomes: Suppose that $f(0),f(1), \cdots $ and $g(0),g(1), \cdots$ are two sequences of positive integers such that $f(0),g(0) \ge 2$ and\[ f(n+1) = \gcd{(f(n),g(n))} + 1, \qquad g(n+1) = \operatorname{lcm}{(f(n),g(n))} - 1. \]Show that the sequence $f(n)$ is eventually periodic; in other words, there exist integers $N \ge 0$ and $t > 0$ such that $f(n+t) = f(n)$ for all $n \ge N$. So $f,g,s\colon \mathbb{Z}_{\ge 0} \to \mathbb{N}$. Let a positive integer $i$ be a peak if $f(i)\ge f(i+1)$. Since $\gcd(f(n),g(n)) \le f(n)$, we have if $n$ is not a peak, then $f(n+1) = f(n) + 1$ and also $g(n+1) = g(n ) - 1$. Let $i_1,i_2,\ldots,$ be all the peaks. Here are some identities about peaks in this problem. 1) $n$ is a peak iff $f(n)\nmid s(n)$. 2) $s(n) = s(n+1) $ if $n$ is not a peak 3) By identity 2, if $i_n$ is a peak, then \[s(i_n+1) = s(i_n+2) \cdots = s(i_{n+1})\] 4) $f(i_1)$ is the smallest positive integer greater than or equal to $f(0)$ not dividing $s(0)$. 5) For any positive integer $x$, $f(i_{x+1})$ is the smallest positive integer greater than or equal to $\gcd(f(i_x),g(i_x))+1$ not dividing \[s(i_{x+1}) = s(i_x + 1) = \gcd(f(i_x),g(i_x)) + \mathrm{lcm}(f(i_x),g(i_x))\] Claim: $f(i_x)\nmid \gcd(f(i_x),g(i_x)) + \mathrm{lcm}(f(i_x), g(i_x))$. Proof: Suppose not. Then since $f(i_x)\mid \mathrm{lcm}(f(i_x),g(i_x))$, we get \[f(i_x)\mid g(f(i_x),g(i_x)),\]which implies $f(i_x)\mid g(i_x)$, contradiction as $i_x$ is a peak. $\square$ Since $f(i_x)\ge \gcd(f(i_x),g(i_x)) + 1$, we have $f(i_{x+1}) \le f(i_x)$. So the sequence $f(i_1), f(i_2),\ldots, $ is nonincreasing, and thus eventually constant, say at $C$. Claim: We have $\gcd(C,s(n))$ is constant for all sufficiently large $n$. Proof: It's obvious that if $n$ is not a peak, then $\gcd(C,s(n)) = \gcd(C, s(n+1))$. It remains to show that if $n$ is a peak, then $\gcd(C,s(n)) = \gcd(C,s(n+1))$. We have \begin{align*} \gcd(C,s(n+1)) \\ = \gcd(f(n), f(n+1) + g(n+1) \\ = \gcd \left(f(n), \gcd(f(n),g(n)) + \mathrm{lcm}(f(n),g(n))\right ) =\gcd(f(n),g(n)) \end{align*} and \[\gcd(C,s(n)) = \gcd(f(n),f(n)+g( n)) = \gcd(f(n),g(n))\] Thus, $\gcd(C,s(n)) = \gcd(C,s(n+1))$. $\square$ Let $\gcd(C,s(n)) = c$ for all sufficiently large $n$. We have $f(n+1) = f(n)+1$ if $n$ is not a peak, and $f(n+1) = c+1$ if $n$ is a peak. So at some point, $f$ will cycle like \[c+1,c+2,\ldots, C, c+1,c+2,\ldots, C,\ldots\]and so on. Hence $f$ is eventually periodic.

Notice $a_i$ increases only when $a_i | b_i$. We say the sequences violates $k-$admittance if $a_i = k, k \nmid b_i$ for some $i$. Now notice if the sequence was most recently a $k-$ violator, then $gcd(a_i, b_i) + lcm(a_i, b_i) = gcd(a_i, b_i)+1 \pmod{k}$ which cannot be $0$, so it cannot "not violate" $k$ before violating some other number, since between that interval the sum of the sequences must stay constant. Since $a_i$ is a sequence that increases by $1$ at most, it follows that the sequence of violations is monotonic decreasing. As according to company policy, if you disobey once, you will not be allowed to return again. Hence eventually the sequence will and must violate the exact same number over and over again. Now notice that each time the sequence violates that number, the next resulting $a_i$ is uniquely determined by the gcd of the $a_i, b_i$, followed by the $a_i$ increasing by one until it reaches the violation number again. Furthermore since the sequence only ever violates at the same number, the gcd divides that number and as a result will divide the sum of the sequences forevermore. Hence the gcd when violating is monotonic increasing after the sequence violates only one number, so it eventually stabilizes as it cannot surpass the violation number, so the $a_i$ from there on must be in the form $s, s+1, s+2, \ldots, s+m, s, s+1, s+2, \ldots, s+m, \ldots$ and so on, cyclically once the gcd becomes constant. Hence it is periodic.

Let $s_{n}=a_n+b_n$. Note that the following four statements are equivalent: $a_n\mid b_n$, $a_{n+1}=a_n+1$, and $b_{n+1}=b_n-1$, $s_{n+1}=s_n$. Now, let $n$ be good if $s_n\neq s_{n+1}$. It can easily be checked that $s_n<s_{n+1}$. Now, let $n_0,n_1,\dots$ describe all good numbers. Then we claim that $a_{n_0}>a_{n_1}>\dots$. Assume otherwise then $a_{n_i}<a_{n_{i+1}}$. Let $a_{n_i}=dp$ and $b_{n_i}=dq$ where $p$ and $q$ are coprime then $a_{n_i+1}=d+1$ and $b_{n_i+1}=dpq-1$ and $s_{n_i+1}=dpq+d$. Now, at some point, by discrete continuity, we must have $a_{j}=dp$ for some $n_i<j<n_{i+1}$ so $b_j=dpq+d-dp$. However, it can easily be checked that $dp\nmid dpq+d-dp$ so $s_{j+1}\neq s_j$, so $j$ is good, contradiction. Therefore, the sequence $a_{n_i}$ is eventually constant. In particular the sequence $a$ is bounded, and $b$ is basically bounded since only some select moduli matter, so by pigeonhole principle, $a$ and $b\pmod{\text{whatever that modulus that matters is}}$ are periodic as desired.

Let an index $i$ be a mountain if $a_i \geq a_{i+1}$. The key idea is the following. Claim: $\{a_k\}$ gets "trapped" below any mountains to its left, like a train tunnel. That is: suppose $i$ is a mountain. Then for all $j \geq i$, we have $a_j \leq a_i$. Proof: We strong induct on $a_i=n$, with the base case of $n=2$ following easily: if $i$ is a mountain with $a_i=2$, then $b_i$ is odd. Then $a_{i+1}=2$ and $b_{i+1}$ is still odd. Now suppose that the claim is true for all numbers less than $n$. Let $b_i=m$ and $\gcd(a_i,b_i)=\gcd(m,n)=d$. Then $a_{i+1}=d+1$ and $b_{i+1}=\tfrac{mn}{d}-1$. From here, if any terms in the sequence are mountains less than $n$, we are done by induction. Otherwise, by induction we have $a_{i+t}=d+t$ and $b_{i+t}=\tfrac{mn}{d}-t$ for all $1 \leq t \leq n-d$; in particular $a_{i+n-d}=n$ and $b_{i+n-d}=\tfrac{mn}{d}-n+d$. Since $\tfrac{m}{d} \in \mathbb{Z}$ it follows that $\gcd(a_{i+n-d},b_{i+n-d})=d$, so $i+n-d$ is a mountain again. Repeating this indefinitely implies the claim. $\blacksquare$ If $i$ is not a mountain then $a_{i+1}=a_i+1$ and $b_{i+1}=b_i-1$, so we cannot have every term in the sequence be a non-mountain, since in this case eventually $a_k>b_k$. Thus $\{a_i\}$ is bounded. Let $M=\max a_i$. Then the value of $b_{i+1} \pmod{M!}$ depends only on $a_i$ and $b_i \pmod{M!}$. On the other hand, there are finitely many pairs $(a_i,b_i \pmod{M!})$, so some pair eventually repeats, and the sequence is periodic past that point. $\blacksquare$ Remark: Hard for an N4? Tricky intuition check

Can someone please check if my proof is correct? It seems similar to #4, but the justification for the second part (proving that the 'heads', or the lowest parts the sequence reaches, is constant) is a bit different. Using the same wording as other solutions in this thread ('peaks'), we start from after proving the peaks are monotonically decreasing. The peaks must eventually become equal to $N$ forever. Now start from a point where $a_i$ is such a peak, i.e. $a_i = N = dx$ and $b_i = dy$, where $d = \gcd(a_i,b_i)$ and $\gcd(x,y) = 1$. Note that $x > 1$ or else this contradicts the fact that $a_i$ is a peak. Then $a_{i+1} = d + 1$ and $b_{i+1} = dxy - 1$, and eventually, by our assumption that $N$ recurs, we have: $$a_j = d + (dx - d) = dx$$$$b_j = dxy - (dx - d) = d(x(y-1)+1)$$ But as $\gcd(x, x(y-1) + 1) = 1$, thus $a_{j+1} = d + 1$, and $b_{j+1} = dx(x(y-1) + 1) - 1$, and by induction this cycle continues.