OliForum Matematico

(IMO Shortlist 2008)
Sia data una sequenza infinita di interi positivi $ a_0,a_1,a_2,\ldots $ tale che $ \text{mcd}(a_{n+2},a_{n+1}) > a_n $ per ogni $ n \in \mathbb{N} $. Mostrare che $ a_n \ge 2^n $ per ogni $ n \in \mathbb{N} $.

notiamo innanzitutto che la sequenza è strettamente crescente

poniamo per assurdo che esista
$ a_n<2^n $

scopriamo che
$ mcd(a_{n-1},a_n)<2^{n-1} $
poichè, se
$ 2^{n-1}-1<mcd(a_{n-1},a_n)<2^n $
implicherebbe che
$ 2^{n-1}-1<a_{n-1}<2^n $
e
$ 2^n-1<x*2^{n-1}<=a_n $
assurdo

iterando il procedimento scopriamo che
$ mcd(a_i,a_{i+1})<2^i $
in particolare
$ mcd(a_1,a_2)=1<2 $
ma
$ a_0<mcd(a_1,a_2)=1 $
impossibile

@exodd: Uhm, il procedimento iniziale fa uso dell'ipotesi di assurdo. Non ho capito come fai a iterarlo. Non hai l'ipotesi di assurdo per tutti gli i ma solo per un certo i=n. Un piccolo suggerimento: il comando \ge produce il maggiore o uguale e il comando \le produce il minore o uguale (per esempio: $ 1\le 2 $).

Sotto ci sono i miei "aiutini" per la soluzione, se non vuoi leggerli non leggerli, odio postare in invisibile...

La mia idea per dimostrarlo era porre $ d_n=(a_n,a_{n+1}) $ e vedere che possiamo supporre che $ a_n=[d_n,d_{n-1}] $ senza perdita di generalità (perché?), dove le parentesi tonde sono il MCD e le quadre il mcm.

L'ipotesi diventa che $ d_n>[d_{n-1},d_{n-2}] $

Ora voglio dimostrare che $ a_n+(a_n,a_{n+1})\ge 2^{n+1} $ (che è più forte della tesi). Lo scrivo come $ [d_n,d_{n-1}]+d_n\ge 2^{n+1} $ e cerco di dimostrarlo per induzione (cioè voglio che $ [d_n,d_{n-1}]+d_n\ge 2[d_{n-1},d_{n-2}]+2d_{n-1} $ ). Hint: considerare $ d_n $ come variabile indipendente che rispetta la nostra ipotesi.