$f_n$ costante per $n$ grande

[Pachisi]

Siano $a$ e $b$ due interi positivi dispari. Definiamo la sequenza $(f_n)$ ponendo $f_1=a, f_2=b$ e $f_n$ il maggiore divisore dispari di $f_{n-1}+f_{n-2}$, $n \ge 3$. Dimostrare che $f_n$ diventa costante per $n$ sufficientemente grande, e trovare questo valore.

[Erasmus_First]

La dimostrazione che chiedi non l'ho fatta.

Ma ... provando e riprovando mi viene sempre 1.
Intuitivamente, mi pare di aver capito perché.
La successione è di numeri sempre dispari; e la somma di due dispari è pari.
Il suo massimo divisore dispari [che sarà il prossimo termine della successione] è al massimo la media aritmetica degli addendi, ma può essere anche di meno (se la media aritmetica è ancora pari). Vuol dire che a lungo andare i numeri calano.
Prima o poi capiterà che la somma degli ultimi due dispari è una potenza di 2, e il suo massimo divisore dispari è allora 1 (ossia il minimo dispari).
Prima o poi capiterà che il penultimo numero dispari sarà del tipo $2^n-1$ e l'ultimo 1. Allora il prossimo è ancora 1 ... ed il giochino termina sulla costante 1.

Qualche esempio:
(27, 79) ––––> 53, 33, 43, 19, 31, 25, 7, 1, 1.
(79, 27) –––> 53, 5, 29, 17, 23, 5, 7, 3, 5, 1, 3, 1, 1.
(127, 253) –––> 95, 87, 91, 89, 45, 67, 7, 37, 11, 3, 7, 5, 3, 1, 1.
(253, 127) –––> 95, 111, 103, 107, 105, 53, 79, 23, 51, 37, 11, 3, 7, 5, 3, 1, 1.

________

[Erasmus_First]

Ripensandoci, credo che la costante in cui cade la successione sia il massimo comune divisore dei due dispari iniziali.[MCD(a, b), ovviamente dispari].
Infatti, [se questo è maggiore di 1], mi resta sempre come fattore dispari del prossimo termine.
Esempio (con i numeri iniziali multipli di 105]:
(1155, 1365) –––> 315, 105, 105.

Si vede che prima, scegliendo a caso i due numeri dispari iniziali, mi sono capitati sempre numeri coprimi [MCD(a, b) = 1].

_______

[Vincent46]

Ci provo.

Supponiamo che $MCD(a,b)=d$, di modo che $f_1=dh, f_2=dk$, con $h, k$ coprimi fra loro. Siano ora $g_1=h, g_2=k$ i termini iniziali di una successione definita per ricorrenza in maniera identica a $f_n$. È facile convincersi che $f_n=dg_n$ per ogni $n$ naturale. Allora possiamo limitarci a studiare le successioni che abbiano, come primi due termini, numeri primi fra loro. In particolare, dimostreremo che una tale successione è definitivamente costante e uguale a $1$, cossicché sarà lecito dedurre che una successione tale che $MCD(a,b)=d$ è definitivamente costante e uguale a $d$.

Allora supponiamo che $a,b$ siano primi fra loro.

Notiamo preliminarmente che, se nella successione compaiono due termini uguali consecutivi, allora essi devono essere $1$, e tutta la successione da lì in avanti sarà uguale a $1$. Infatti, se nella sequenza compaiono in fila numeri $a_1, a_2, a_3$ tali che $d = MCD(a_2, a_3)$, allora, procedendo a ritroso, si ha che $a_3 | (a_2+a_1)$, cioé $rd=sd+a_1$ per qualche $r, s$ naturale, e quindi $d|a_1$. Si può procedere a ritroso fino all'inizio della successione, e ottenere che $d|a$ e $d|b$. Perciò $d=1$. Dunque, due numeri successivi uguali nella sequenza devono avere $MCD$ pari a $1$ e, perciò, devono essere essi stessi uguali a $1$.

Osserviamo che, poiché $f_n$ è dispari e divide $f_{n-1}+f_{n-2}$, che è chiaramente pari per ogni $n$, necessariamente si avrà $f_n \leq \frac{f_{n-2}+f_{n-1}}{2}$. Di modo che la successione sarà minore o uguale, termine a termine, della seguente successione:

\[a, b, \frac{a+b}{2}, \frac{a+3b}{4}, \, ...\]
dove ogni termine a partire da $n=3$ consiste nella semisomma dei due precedenti.

È facile convincersi che $f_3$ e $f_4$ sono strettamente minori di $M = \max\{a,b\}$ (ricordiamo che $a$ e $b$ non possono essere uguali, perché sono coprimi; il caso $a=b=1$ è banale). Allora $M' = \max\{f_3, f_4\} < M$. inoltre possiamo supporre che $f_3 \ne f_4$; altrimenti, per l'osservazione fatta all'inizio, si dovrebbe avere $f_3 = f_4 = 1$ e l'esercizio sarebbe concluso.

Ripetendo il ragionamento, si trova che $f_5, f_6 < M'$. E così via: ogni due indici, l'asticella del valore massimo ammissibile per $f_n$ cala di almeno $1$. Perciò, in un numero finito di passi, si arriva a concludere che il limite superiore per i valori ammissibili per $(f_n)$ vale proprio $1$, come volevasi dimostrare.

[Pachisi]

Si