Intanto poniamo $ \displaystyle~b_n=(a_n,a_{n+1}) $ per ogni $ \displaystyle~n\ge 0 $.
Consideriamo la sequenza $ \displaystyle~\{c_n\} $ con $ \displaystyle~c_0=b_0 $ e $ \displaystyle~c_{n+1}=\textrm{lcm}(b_n,b_{n+1}) $ per ogni $ \displaystyle~n\ge 0 $.
Questa rispetta ancora tutte le ipotesi: dato che $ \displaystyle~b_{n+1}\mid c_{n+1} $ e $ \displaystyle~b_{n+1}\mid c_{n+2} $, $ \displaystyle~(c_{n+1},c_{n+2})\ge b_{n+1}=(a_{n+1},a_{n+2})>c_n,~\forall n\ge 0 $. Inoltre $ \displaystyle~c_0=b_0\le a_0 $ e dato che $ \displaystyle~b_n\mid a_{n+1} $ e $ \displaystyle~b_{n+1}\mid a_{n+1} $ abbiamo $ \displaystyle~c_{n+1}\mid a_{n+1}~(*) $, quindi $ \displaystyle~c_{n+1}\le a_{n+1} $.
Dunque basta far vedere che $ \displaystyle~c_n\ge 2^n~\forall n\ge 0 $ per avere la tesi.
Scusate questo ciarpame di successioni, potevo sostituire tutto con un bel wlog ma così è più rigoroso..
Dopo aver semplificato la successione, ci accorgiamo che, essendo $ \displaystyle~c_n\mid a_n~\forall n\ge 0~(*) $, $ \displaystyle~(c_n,c_{n+1})\mid b_n $ che unito a $ \displaystyle~b_n\mid (c_n,c_{n+1}) $ dà $ \displaystyle~(c_n,c_{n+1})=b_n $. Quindi possiamo sbarazzarci dei $ \displaystyle~\{c_n\} $, visto che ora ipotesi e tesi sono esprimibili con i soli $ \displaystyle~\{b_n\} $:
Problema 74 (2^ edizione)
La sequenza di interi positivi $ \displaystyle~b_0,b_1,b_2,\ldots $ rispetta le ipotesi $ \displaystyle~b_{n+1}>\textrm{lcm}(b_n,b_{n-1})~\forall n\ge 1 $ e $ \displaystyle~b_1>b_0 $. Allora $ \displaystyle~(b_n,b_{n-1})\ge 2^n $ (e $ \displaystyle~b_0\ge 1 $
).
Dalle ipotesi $ \displaystyle~\{b_n\} $ è strettamente crescente. Mostriamo la tesi per $ \displaystyle~n=1,2,3,4 $:
n=1 $ \displaystyle~b_1>b_0\ge 1 $ quindi $ \displaystyle~b_1\ge 2 $ e $ \displaystyle~\textrm{lcm}(b_1,b_0)\ge 2 $
n=2 $ \displaystyle~b_2>\textrm{lcm}(b_1,b_0)\ge 2 $ (v. qui sopra) e quindi è almeno 3. Se $ \displaystyle~b_2=3 $, $ \displaystyle~1<b_1<b_2=3 $ da cui $ \displaystyle~b_1=2 $ e $ \displaystyle~\textrm{lcm}(b_2,b_1)=6>4 $, altrimenti $ \displaystyle~b_2\ge 4 $ e $ \displaystyle~\textrm{lcm}(b_2,b_1)\ge 4 $
n=3 $ \displaystyle~b_3>\textrm{lcm}(b_2,b_1)\ge 4 $ e se fosse $ \displaystyle~\textrm{lcm}(b_3,b_2)<8 $ allora $ \displaystyle~\textrm{lcm}(b_3,b_2) $ dovendo essere multiplo di $ \displaystyle~b_3 $ dovrebbe essere proprio $ \displaystyle~b_3 $, da cui $ \displaystyle~b_2\mid b_3 $, quindi $ \displaystyle~b_3 $, non potendo essere primo ($ \displaystyle~b_2>2 $), dovrebbe essere 6, da cui $ \displaystyle~b_2=3 $ e $ \displaystyle~b_1=2 $ (assurdo per l'ipotesi $ \displaystyle~b_3>\textrm{lcm}(b_2,b_2) $)
n=4 anche qui supponiamo per assurdo che $ \displaystyle~(b_3,b_4)<16 $; allora $ \displaystyle~8<b_4<16 $ con $ \displaystyle~b_3\mid b_4 $. Essendo $ \displaystyle~b_4 $ composto con un divisore proprio maggiore di 4 ($ \displaystyle~b_3 $) deve essere $ \displaystyle~b_4\in\{10,12,14,15\} $. Se $ \displaystyle~b_4\in\{10,15\} $, $ \displaystyle~b_3=5 $ da cui, essendo $ \displaystyle~b_2\ge 3 $ e coprimo con 5, $ \displaystyle~15\ge b_4>\textrm{lcm}(b_2,b_3)=5b_2\ge 15 $, assurdo. Se $ \displaystyle~b_4=14 $, $ \displaystyle~b_3=7 $ che di nuovo è coprimo con $ \displaystyle~b_2 $ e dà un assurdo come sopra (14>21). Se $ \displaystyle~b_4=12 $, $ \displaystyle~b_3=6 $ e $ \displaystyle~\textrm{lcm}(b_3,b_2)=b_3 $ (sempre per l'ipotesi $ \displaystyle~b_4>\textrm{lcm}(b_3,b_2) $) quindi $ \displaystyle~b_2=3 $ e $ \displaystyle~b_1=2 $, assurdo perché deve essere $ \displaystyle~b_3>\textrm{lcm}(b_2,b_1) $
A questo punto supponiamo per assurdo che $ \displaystyle~n\ge 5 $ sia il minimo per cui non vale la tesi, cioè $ \displaystyle~\textrm{lcm}(b_n,b_{n-1})<2^n $. Useremo implicitamente il fatto che $ \displaystyle~b_k>\textrm{lcm}(b_{k-1},b_{k-2})\ge 2^{k-1},~\forall 2\le k\le n $.
Passo 1. Poiché $ \displaystyle~b_n>2^{n-1} $, $ \displaystyle~\textrm{lcm}(b_n,b_{n-1}) $, essendo suo multiplo minore del suo doppio, deve essere proprio $ \displaystyle~b_n $, quindi $ \displaystyle~b_{n-1}\mid b_n $. Ma se $ \displaystyle~b_n\ge 4 b_{n-1} $, $ \displaystyle~b_n>4\cdot 2^{n-2}=2^n $ assurdo. Se $ \displaystyle~b_n=2b_{n-1} $, poiché $ \displaystyle~b_n>\textrm{lcm}(b_{n-1},b_{n-2}) $ (che è multiplo di $ \displaystyle~b_{n-1} $), $ \displaystyle~\textrm{lcm}(b_{n-1},b_{n-2})=b_{n-1} $, quindi $ \displaystyle~b_{n-1}\ge 2^{n-1} $ per ipotesi e $ \displaystyle~b_n>2^n $, assurdo. Quindi $ \displaystyle~b_n=3b_{n-1} $.
Passo 2. Sempre per $ \displaystyle~b_n>\textrm{lcm}(b_{n-1},b_{n-2}) $, questo $ \displaystyle~\textrm{lcm} $ può essere solo $ \displaystyle~b_{n-1} $ o $ \displaystyle~2b_{n-1} $. Nel primo caso otteniamo un assurdo come sopra, quindi $ \displaystyle~2b_{n-1}=kb_{n-2} $ con $ \displaystyle~k>2 $ dispari (altrimenti $ \displaystyle~b_{n-2}\mid b_{n-1} $). Quindi $ \displaystyle~2^n>b_n=3b_{n-1}=\frac{3k}{2}b_{n-2}>\frac{3k}{2}\cdot 2^{n-3} $, da cui $ \displaystyle~k\le 5 $.
Se $ \displaystyle~k=3 $, $ \displaystyle~b_{n-1}=\frac{3}{2}b_{n-2} $ e $ \displaystyle~\textrm{lcm}(b_{n-2},b_{n-3})=b_{n-2} $ (deve essere $ \displaystyle~<\frac{3}{2}b_{n-2} $), quindi $ \displaystyle~b_{n-2}\ge 2^{n-2} $ e $ \displaystyle~b_n=\frac{9}{2}b_{n-2}>2^n $ assurdo. Rimane il caso $ \displaystyle~k=5 $. Non ci arrendiamo e continuiamo fiduciosi il delirio.
Passo 3. Per non cadere in un assurdo come prima, poiché $ \displaystyle~\textrm{lcm}(b_{n-2},b_{n-3})<\frac{5}{2}b_{n-2} $, deve essere $ \displaystyle~\textrm{lcm}(b_{n-2},b_{n-3})=2b_{n-2} $. Sia quindi di nuovo $ \displaystyle~2b_{n-2}=k'b_{n-3} $ con $ \displaystyle~k' $ dispari: da $ \displaystyle~2^n>b_n=\frac{15}{2}b_{n-2}=\frac{15k'}{4}b_{n-3}>\frac{15k'}{4}\cdot 2^{n-4} $ otteniamo $ \displaystyle~k'\le 4 $, cioè $ \displaystyle~k'=3 $. Finalmente essendo $ \displaystyle~b_{n-2}=\frac{3}{2}b_{n-3} $ abbiamo $ \displaystyle~\textrm{lcm}(b_{n-3},b_{n-4})=b_{n-3} $, quindi $ \displaystyle~b_{n-3}\ge 2^{n-3} $ e $ \displaystyle~b_n=\frac{45}{4}b_{n-3}\ge 45\cdot 2^{n-5}>2^n $, assurdo.
Puff pant
che problema bastardo!
Aspetto conferme da Dario/Federico..