Sequenze di divisori dispari

[salva90]

Viene da un vecchio usamo ma non chiedetemi quale...

Definiamo una sequenza come segue:

$ ~f_1=a $
$ ~f_2=b $
$ ~f_n=g(f_{n-2}+f_{n-1}) $ per $ n\ge3 $

dove a e b sono interi positivi dispari e $ g(k) $ indica il più grande divisore dispari di k.


Dimostrare che per n abbastanza grande la successione è costante e determinarne l'eventuale valore

good luck by salva

[marco-daddy]

Lemma 1:$ (f_{n-1},f_{n-2})|f_n $
Dimo: segue da come è definita $ g(k) $

Ora sia $ \displaystyle2^k\|f_{n-1}+f_{n-2} $

$ \displaystyle f_{n}=\frac{f_{n-1}+f_{n-2}}{2^k}\leq\frac{f_{n-1}+f_{n-2}}{2}\leq\max\{f_{n-1},f_{n-2}\} $

Se $ f_{n-1}=f_{n-2} $ la successione diventa costante

Mettiamo per assurdo che la successione non diventi mai costante e definiamo $ \alpha_i=\max\{f_{i},f_{i+1}\} $
Quest'ultima successione è strettamente decrescente per ipotesi
Tuttavia non esiste una successione infinita strettamente decrescente definita sui naturali.

Ora sia d il valore costante della successione.

Dal lemma 1 applicato su tutta la successione $ (a,b)|d $
Inoltre esistono $ f_{i-2}, f_{i-1} $ t.c. $ g(f_{i-2} + f_{i-1})=d $ e $ g(f_{i-1}+d)=d $ ma per il lemma 1 $ d|f_j $con$ j\leq i $ compresi a e b

Quindi $ d=(a,b) $

[Jacobi]

Viene da un vecchio usamo ma non chiedetemi quale...

USAMO 1993 ( mi e' capitato per caso fra le mani una dispensa di teoria dei numeri con quest'esercizio )