We have $f_{n+1}\le\frac{f_n+f_{n-1}}2\ (*)$. Let's prove that in general, such a sequence with positive terms converges to its infimum. Let $e_n=\max(f_n,f_{n+1})$. It's clear from $(*)$ that $e_n$ is a decreasing sequence, so it must have a limit $\ell\ge 0$. Of course, we always have $f_n\le e_n$. Suppose there is an $\varepsilon>0$ such that we can find arbitrarily many values of $n$ for which $f_n<\ell-3\varepsilon$. Take such an $n$ large enough that $f_{n-1}=e_{n-1}<\ell+\varepsilon$. We then get $f_{n+1}\le\frac{f_n+f_{n-1}}2<\ell-\varepsilon$, which means that $e_n=\max(f_n,f_{n+1})<\ell-\varepsilon$, and this is absurd (the sequence $e_n$ decreases towards $\ell$, so all its terms must be $\ge\ell$). Now, when we apply this to the sequence $(f_n)_n$ in our problem, we find it to be convergent to some $\ell$ and thus eventually equal to $\ell$, since its terms are positive integers. Since all the terms $f_n$ are clearly divisible by $d=(a,b)$, we have $d|\ell\ (\#)$. On the other hand, if not ll terms $f_n$ are divisible by $\ell$, then there will be a last term $f_n$ not divisible by $\ell$, but then $f_n+f_{n+1}$ wouldn't be divisible by $\ell$ either, which means that $\ell\not|f_{n+2}$, contradicting the fact that $f_n$ was the last one. This means that $\ell|f_n,\ \forall n$, and, in particular, $\ell|a,b\Rightarrow \ell|d$. Together with $(\#)$, this gives $\ell=(a,b)$.

We first prove that for any $ n$, $ \max \{f_{n-1}, f_n\} \ge \max \{f_n, f_{n+1} \}$. If $ f_{n-1} \ge f_n$, then the left hand side is $ f_{n-1}$. Also, since two odd numbers add to an even number, $ \frac{f_{n-1} + f_n}{2} \ge f_{n+1}$ $ \Rightarrow f_{n-1} + f_n \ge 2f_{n+1}$ $ \Rightarrow f_{n-1} + f_{n-1} \ge 2f_{n+1}$ $ \Rightarrow f_{n-1} \ge f_{n+1}$. Since $ f_{n-1} \ge f_n$ and $ f_{n-1} \ge f_{n+1}$, we must have $ f_{n-1} \ge \max \{f_n, f_{n+1} \}$. Similarly, if $ f_n \ge f_{n-1}$, then the left hand side is $ f_n$. Also, $ \frac{f_{n-1} + f_n}{2} \ge f_{n+1}$ $ \Rightarrow f_{n-1} + f_n \ge 2f_{n+1}$ $ \Rightarrow f_n + f_n \ge 2f_{n+1}$ $ \Rightarrow f_n \ge f_{n+1}$ $ \Rightarrow f_n \ge \max \{f_n, f_{n+1} \}$. This means that the sequence of maximums of adjacent terms is non-increasing. Since all terms must be positive integers, the sequence of maximums must eventually become constant. If the sequence of maximums eventually becomes constant, either the sequence of $ \{ f_n \}$ becomes constant or it eventually alternates between two different numbers. Suppose, for the sake of contradiction, that the sequence alternates between two different numbers. Then we eventually have the terms $ x, y, x, y, x, y \ldots$. This implies that $ x$ is the greatest odd divisor of $ x + y$, and that $ y$ is the greatest odd divisor of $ y + x$. However, since $ x + y = y + x$, and $ x, y$ are both the greatest odd divisor of $ x + y$, we must have $ x = y$. This contradicts the assumption that the sequence alternates between two different numbers. Therefore, the sequence eventually becomes constant. Now, suppose that $ (a, b) = d$. Clearly, $ d$ is not even. Therefore, $ f_3 = \frac{a + b}{2^\text{something}}$ is also divisible by $ d$. Inductively, we can see that all terms of the sequence $ \{ f_n \}$ are divisible by $ d$. If we divide all terms by $ d$ to form a new sequence, then the first two terms must be relatively prime odd numbers; suppose these relatively prime odd numbers are $ a^\prime, b^\prime$. Then the next term is $ \frac{a^\prime + b^\prime}{2^\text{something}}$, which must be relatively prime to $ b^\prime$. Inductively, we can see that every pair of adjacent terms of the new sequence must be relatively prime. But we proved that the original sequence must become constant. Therefore, the new sequence must also become constant (since constants divided by constants are still constants). If the new sequence becomes constant and every pair of adjacent terms is relatively prime, then it must eventually become $ 1$, since 1 is the only number that is relatively prime to itself. Since we divided terms of the original sequence by $ d$ to form their corresponding terms in the new sequence, we know the original sequence converged to $ d$. Then the sequence $ \{ f_n \}$ eventually becomes constant, and eventually equals $ (a, b)$.

The eventual value for $ a,b$ is $ gcd(a,b)$$ \Leftrightarrow$ that for all coprime $ a,b$ is $ 1$, So Proof: WLOG, assume that $ a,b$ coprime, then Certainly we have $ g_n = f_n + f_{n + 1}$ is strictly decreasing until $ f_n = f_{n + 1}$ (then $ g_n$ and thus $ f_n$ will remain at that value). Obviously, it will attain an eventual value because $ g_n > 0$ cannot strictly decrease infinitely many times. So we can find $ f_n = f_{n + 1} = p$, where $ p$ is the eventual value for a large enough $ n$ . Then we get $ p|f_{n - 1}$, similarly by induction we know $ p$ divides both $ a$ and $ b$ $ \Leftrightarrow p = 1$, which is what we want to prove.

We claim that the sequence eventually becomes constant at the greatest odd divisor of $f_1, f_2$. We will first show by induction on $\max(f_1,f_2)$ that if $f_1, f_2$ are odd, coprime integers, the sequence eventually becomes constant at 1. Note that the base case of $f_1=1, f_2=1$ is trivial. Now, assume that the result holds for $1\le\max(f_1,f_2)\le2n-1$. Then, let $\max(f_1,f_2)=2n+1$. We have two cases: 1. $f_1>f_2$: Note that $f_1+f_2$ is even and thus, \[ f_3|\frac{f_1+f_2}{2}\\ \Rightarrow f_3\le\frac{f_1+f_2}{2}<\max(f_1,f_2) \] Now, $\max(f_2,f_3)<f_1=2n+1$ and thus, by the inductive hypothesis, we may conclude. 2. $f_2>f_1$: Similarly to above, $f_3\<\max(f_1,f_2)=f_2$. Further note that $f_4|\frac{f_2+f_3}{2}$ and thus, $f_4<f_2$ and so, $\max(f_3,f_4)<f_2=2n+1$ and, again, by the inductive hypothesis, we may conclude. Now, note that if $(f_1, f_2)$ is odd, then this odd factor divides all $f_i$, and thus, the sequence is the same as that starting with $\frac{f_1}{(f_1,f_2)},\frac{f_2}{(f_1,f_2)}$ except scaled up by $(f_1,f_2)$. Thus, we have that the result holds for all pairs of odd numbers $f_1,f_2$. Finally, consider the case that $f_1=2^aq, f_2=2^bp$ where $p,q$ are odd integers. Then, $f_3=\frac{f_1+f_2}{2^\min{(a,b)}}$, $f_4=f_2+f_3$. Note that $f_3,f_4$ are odd so the sequence eventually becomes constant at their greatest common factor. Now, note that the greatest odd divisor of $f_1,f_2$ divides both $f_3,f_4$ because they are linear combinations of $f_1,f_2$ (only divided by powers of 2). Further note that the greatest common $f_3,f_4$ divides $f_1,f_2$ because $f_2=f_4-f_3$ and $f_1=(2^{\min{(a,b)}}+1)(f_3)-f_4$. Thus, the result holds for any two integers $f_1,f_2$ and we conclude. The cases where $f_1,f_2$ are even, odd or odd, even follow similarly; in particular, the sequence becomes odd by $f_3,f_4$ by definition, so it becomes repeating, and then we find by linear combinations that the greatest odd divisor of $f_3,f_4$ is the same as that of $f_1,f_2$.

We claim that the sequence stays constant at $\gcd(a,b)$. Lemma 1: $\min\{f_k\}=\gcd(a,b)$ Proof: For every pair we have: $$f_{n-1}+f_{n} \rightarrow f_{n+1} \implies f_{n-1}+f_{n} \rightarrow \gcd(f_{n-1},f_{n})*\text{stuff},$$where $\text{stuff}=\frac{a+b}{\gcd(f_{n-1},f_{n})*2^{v_{2}(a+b)}},$ which is clearly an integer. Now since the $\gcd(f_{n-1},f_{n})$ will always be preserved under this operation, this implies the result. Also, note that $f_{a+2} \le \max\{f_a, f_{a+1}\}$, since at "worst" we are dividing by two (taking the average). Thus we can see that for any pair of consecutive elements, the maximal term of that pair will be replaced in the proceeding term. This reduction can be repeated indefinitely, until we reach the particular minimum of $\gcd(a,b)$, which proves our claim.

An idea for exploration: What is the value of the minimum $n$ (in terms of $a$ and $b$) before $f_n$ i.e. what is the length of the sequence of $f_i$ before it becomes constant?

We have the inequality \[f_n \leq \frac{f_{n-1}+f_{n-2}}{2} \]without loss of generality suppose $f_{n-1}>f_{n-2}$ (in the case were both are equal the sequence would be alredy constant) Then $f_{n-1} > \frac{f_{n-1}+f_{n-2}}{2}$ and thus greater than $f_{n}$. Now we have that the sequence is reduced in every move and thus can not get infinite values(in fact it will continue until all terms are constant) Suppose the $gcd(a, b) = k$ then we have that $a + b = k(l + k)$ for some integers k and l. Now, since all elements in the set contain k, and the sequence is reducing, it follows that it will mantain at k Thus the sequence will be constant for $gcd(a, b)$

FTSOC, assume that the sequence is not eventually constant.So by the condition $f_n\ne f_{n+1}$,for all $n$.Then we have:$$f_n=\frac{f_{n-1}+f_{n-2}}{2^{stuff}}\le \frac{f_{n-1}+f_{n-2}}{2}<\max(f_{n-1},f_{n-2})$$Also we have:$$f_{n+1}\le \frac{f_n+f_{n-1}}{2}<\max(f_n,f_{n-1})\le \max(f_{n-1},f_{n-2})$$Hence,we have: $\max(f_{n+1},f_n)<max(f_{n-1},f_{n-2})\qquad {(*)}$ As,there can't exist a strictly decreasing sequence of positive integers ,this contradicts $(*)$$\blacksquare$ We claim that the eventual value of the sequence $f_n$ is $gcd(a,b)$.It is easy to verify that all the terms of the sequence is divisible by $gcd(a,b)$. Suppose $x$ be the eventual value of this sequence .[So,$gcd(a,b)|x$.]And $n$ be the first index,starting from which every number is $x$.Then $f_{r-1}=2^{stuff}f_{r+1}-f_r$ gives $x|f_{n-1}$.Inductively,we have $x|f_i$ for all $i\le n$.In particular,$x|a$ and,$x|b$.So $x|gcd(a,b)$. Hence,$x=gcd(a,b)$.The conclusion follows.$\blacksquare$

Notice $f_n=\tfrac{f_{n-1}+f_{n-2}}{2^k}$ for some $k\ge 1$ since $f_n$ is always odd. Notice if $f_{n-1}=f_{n-2},$ then $f_n=2f_{n-1}/2^k=f_{n-1}.$ Hence, if $2$ consecutive terms in the sequence are equal, then the sequence becomes constant. Assume FTSOC that $f_{n-1}\neq f_{n-2}$ for all $n.$ Then, $$f_n\le\frac{f_{n-1}+f_{n-2}}{2}<\frac{2\max\{f_{n-1},f_{n-2}\}}{2^k}=\max\{f_{n-1},f_{n-2}\}$$and $$f_{n+1}<\max\{f_n,f_{n-1}\}\le \max\{f_{n-1},f_{n-2}\}$$so $\max\{f_n,f_{n+1}\}<\max\{f_{n-1},f_{n-2}\}.$ If we let $m_n=\max\{f_n,f_{n+1}\},$ we see $$m_1>m_3>m_5>m_7>\dots,$$which is a contradiction as $m_i$ are positive integers. Hence, $f_n=c$ for some $i\ge n_0.$ We claim that $d=\gcd(a,b)\mid f_n$ for all $n.$ We proceed by strong induction. For our base cases $n=1,2$ clearly $d\mid a,b.$ For our inductive step, assume $d\mid f_{n-1},f_{n-2}.$ Then, $d\mid f_n=\tfrac{f_{n-1}+f_{n-2}}{2^k}$ and our induction is complete. Hence, $d\mid c.$ We proceed by strong induction downwards to show for all $n\le n_0+1,$ we have $c\mid f_n.$ For our base cases, $c=f_{n_0}=f_{n_0+1}.$ For our inductive step, if $c\mid f_{n+1},f_{n+2},$ then $c\mid 2^kf_{n+2}-f_{n+1}=f_n.$ Therefore, $c\mid a,b$ so $c\mid d,$ and $c=d=\gcd(a,b).$ $\square$

Aryth wrote: We first prove that for any $ n$, $ \max \{f_{n-1}, f_n\} \ge \max \{f_n, f_{n+1} \}$. If $ f_{n-1} \ge f_n$, then the left hand side is $ f_{n-1}$. Also, since two odd numbers add to an even number, $ \frac{f_{n-1} + f_n}{2} \ge f_{n+1}$ $ \Rightarrow f_{n-1} + f_n \ge 2f_{n+1}$ $ \Rightarrow f_{n-1} + f_{n-1} \ge 2f_{n+1}$ $ \Rightarrow f_{n-1} \ge f_{n+1}$. Since $ f_{n-1} \ge f_n$ and $ f_{n-1} \ge f_{n+1}$, we must have $ f_{n-1} \ge \max \{f_n, f_{n+1} \}$. Similarly, if $ f_n \ge f_{n-1}$, then the left hand side is $ f_n$. Also, $ \frac{f_{n-1} + f_n}{2} \ge f_{n+1}$ $ \Rightarrow f_{n-1} + f_n \ge 2f_{n+1}$ $ \Rightarrow f_n + f_n \ge 2f_{n+1}$ $ \Rightarrow f_n \ge f_{n+1}$ $ \Rightarrow f_n \ge \max \{f_n, f_{n+1} \}$. This means that the sequence of maximums of adjacent terms is non-increasing. Since all terms must be positive integers, the sequence of maximums must eventually become constant. If the sequence of maximums eventually becomes constant, either the sequence of $ \{ f_n \}$ becomes constant or it eventually alternates between two different numbers. Suppose, for the sake of contradiction, that the sequence alternates between two different numbers. Then we eventually have the terms $ x, y, x, y, x, y \ldots$. This implies that $ x$ is the greatest odd divisor of $ x + y$, and that $ y$ is the greatest odd divisor of $ y + x$. However, since $ x + y = y + x$, and $ x, y$ are both the greatest odd divisor of $ x + y$, we must have $ x = y$. This contradicts the assumption that the sequence alternates between two different numbers. Therefore, the sequence eventually becomes constant. Now, suppose that $ (a, b) = d$. Clearly, $ d$ is not even. Therefore, $ f_3 = \frac{a + b}{2^\text{something}}$ is also divisible by $ d$. Inductively, we can see that all terms of the sequence $ \{ f_n \}$ are divisible by $ d$. If we divide all terms by $ d$ to form a new sequence, then the first two terms must be relatively prime odd numbers; suppose these relatively prime odd numbers are $ a^\prime, b^\prime$. Then the next term is $ \frac{a^\prime + b^\prime}{2^\text{something}}$, which must be relatively prime to $ b^\prime$. Inductively, we can see that every pair of adjacent terms of the new sequence must be relatively prime. But we proved that the original sequence must become constant. Therefore, the new sequence must also become constant (since constants divided by constants are still constants). If the new sequence becomes constant and every pair of adjacent terms is relatively prime, then it must eventually become $ 1$, since 1 is the only number that is relatively prime to itself. Since we divided terms of the original sequence by $ d$ to form their corresponding terms in the new sequence, we know the original sequence converged to $ d$. Then the sequence $ \{ f_n \}$ eventually becomes constant, and eventually equals $ (a, b)$. Wait, Is it a decreasing sequence? It is not given increasing or decreasing sequence.

Let $\gcd(a,b) = d$. We claim that $f_n \equiv d$ for all $n \geq N$ where $N$ is a sufficiently large positive integer. Claim. $d \mid f_n$ for all $n \geq 1$. Proof. We use strong induction. The base case is trivial, so suppose $d \mid f_m$ for all $m \leq k$. Then, the given condition is equivalent to $$f_{k+1} = \dfrac{f_{k}+f_{k-1}}{2^{\nu_2(f_{k}+f_{k-1})}}.$$Since $d \mid f_k, f_{k-1}$, we have $d \mid f_k + f_{k-1}$. Further, $d$ is odd, so $\gcd(d, 2^{\nu_2(f_{k}+f_{k-1})}) = 1$, implying the claim. $\blacksquare$ Claim. $\mathrm{max}\{f_{k+2}, f_{k+3}\} \leq \mathrm{max}\{f_{k+1}, f_k\}$ for every $k \geq 1$. Proof. By definition, \begin{align*} f_{k+2} = \dfrac{f_k + f_{k+1}}{2^{\nu_2(f_k+f_{k+1})}} &\leq \dfrac{f_k+f_{k+1}}{2} \, \, \, \text{(since $f_k$ and $f_{k+1}$ are both odd)} \\ &\leq \mathrm{max}\{f_{k+1}, f_k\}. \end{align*}We can also obtain that \begin{align*} f_{k+3} = \dfrac{f_{k+1}+f_{k+2}}{2^{\nu_2(f_{k+1}+f_{k+2})}} &\leq \dfrac{f_{k+1}+f_{k+2}}{2} \\ &\leq \mathrm{max}\{f_{k+1}, f_k\} \end{align*}so the claim follows. $\blacksquare$ For the sake of contradiction, suppose that $f_n$ is not eventually constant. Then, equality does not always occur in the inequality above, so $f_n$ is weakly decreasing for all positive integers $n$, but $f_n \in \mathbb{Z^+}$, absurd. Thus, $f_n$ is eventually constant. Now, again for a contradiction, suppose $f_n$ is eventually constant at $c$ where $c \neq d$ is a multiple of $d$. Then, we claim that $c \mid f_n$ for all positive integers $n$. To see this, note that if $f_{k+1} = k_1c, f_{k+2}=k_2c$ for odd integers $k_1,k_2$, then we have $$f_k+k_1c = 2^{\nu_2{(f_k+k_1c)}} k_2c$$so $c \mid f_k$, and the claim is given by inductively working backwards. Then, it must be the case that $$\begin{cases} c \mid a \\ c \mid b \end{cases}$$and this implies that $c \mid \gcd(a,b) = d$, but $d \mid c$, so $c=d$, and we are done. $\blacksquare$