I need proof that this is true for all the numbers odd

Question

I need proof this.

let $a,b$ be integers odd, now, define the following sequence.

$f_1=a$

$f_2=b$

$f_n$ for $n≥3$ It corresponds the greatest odd divisor of $f_{n-2}+f_{n-1}$

for example

$$a=123$$ $$b=213$$

$f_1=123$,$f_2=213$,$f_3=21$,$f_4=117$,$f_5=69$,$f_6=93$,$f_7=81$,$f_8=87$,$f_9=21$,$f_{10}=27$,$f_{11}=3$,$f_{12}=15$,$f_{13}=9$,$f_{14}=3$,$f_{15}=3$,$f_{16}=3$,...,,$f_{n}=3$

Now how we can see , after of $f_{14}$ all the termins are $3$

Ok. note that

$$gcd(a,b)=gcd(123,213)=3$$

Now I need proof that this is true for all the numbers odd..

$a.$ It is not satisfy for a and b multiples

$b.$ i dont speak englis, im sorry for orthography

Answer 1

Note that $k = \gcd(a,b)$ is odd and $a = u~k, b = v~k$. Then $a + b = (u + v) ~k$ and if $\omega(n)$ is the greatest odd divisor of $n$ then $\omega(a + b) = \omega(u + v) ~k$.

Since $a + b$ is even, $\omega(a + b) \le (a + b)/2$, proving a sort of general decrease in the values used unless $a = b$, in which case you get a stagnant sequence like $5, 5, 5, 5,\dots$, but this is trivially OK. But if $a \ne b$ then $\omega(a + b) < \max(a, b)$ and you get a decrease that must eventually tend to some limit. However this limit must be $k$ or greater because all of the numbers $a, b, \omega(a + b)$ are divisible by $k$.

So we're left with proving that $\gcd(b, \omega(a + b)) = k$ to prove that we do not introduce any new factors with every new step. This is only the case if $\gcd(u, \omega(u + v)) = s \ne 1$. Then we have $u = m~s,\;u + v = n~s$ for some odd $s$, and we find out that both $u$ and $v$ are divisible by some odd $s \ne 1$, but that means that $k$ was not $\gcd(a,b)$, rather $k~s$ was. Since that's a contradiction, the result cannot possibly have any new factors.

The same property that $\gcd(c, \omega(c + d)) = \gcd(c, d)$ will give you the property that you can only reach a fixed point on the actual GCD, and then the proof is done: the numbers keep decreasing until the fixed point, which is the actual GCD.

Answer 2

First verify that the greatest common divisor of each pair of consecutive elements is constant: $\gcd(f_1,f_2) = \gcd(f_2,f_3) = \gcd(f_3,f_4) = \cdots$. Then verify that each term is at most the average of the two previous terms: $f_n \le \frac12(f_{n-1}+f_{n-2})$. In particular, if we define $m_n = \max\{f_{n-1},f_n\}$, then $\{m_n\}$ is a decreasing sequence ($m_{n+1}\le m_n$); and it strictly decreases every two steps unless the $f$-sequence has become constant ($m_{n+2} < m_n$ unless $f_{n-1}=f_n=\cdots$). Furthermore $m_n\ge1$ for all $n$. Therefore eventually the $m$-sequence must become constant, which implies that the $f$-sequence must be constant; and by the preservation of gcds, that constant value must be $\gcd(f_1,f_2)$.