125. $(a_{i+2},a_{i+1})>a_i$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
nobu
Messaggi: 118
Iscritto il: 06 gen 2012, 13:56

125. $(a_{i+2},a_{i+1})>a_i$

Messaggio da nobu » 26 ago 2012, 22:51

Sia $a_0,a_1,a_2,...$ una successione di numeri interi positivi tali che $(a_{i+2},a_{i+1})>a_i$ per ogni $i\geq0$.
Dimostrare che $a_n\geq 2^n$ per ogni $n\geq 0$.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 125. $(a_{i+2},a_{i+1})>a_i$

Messaggio da jordan » 26 ago 2012, 23:09

Sono bboypa su Mathlinks, e ricordavo di aver risolto questo problema tempo addietro, difatti:
bboypa ha scritto:
April ha scritto:Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i + 1}) > a_{i - 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$.
Our aim $ a_n \ge 2^n$(*) is true for $ n \in \{0,1\}$, in fact $ a_1=1$ would imply $ 1= (a_2,a_1)>a_0 \in \mathbb{N}_0$, absurd. It is also true that $ \{a_n\}_{n \in \mathbb{N}}$ is strictly incrasing since $ \min\{a_{n+1},a_{n+2}\}$ $ \ge (a_{n+1},a_{n+2})$ $ >a_n$. Now if (*) is true for $ n \in \{0,1,\ldots,n-1\}$ then it is true also for $ n$: in fact we have $ a_n-a_{n-1}$ $ \ge (a_n-a_{n-1},a_{n-1})$ $ =(a_n,a_{n-1}) >a_{n-2} \implies$ $ a_n > a_{n-1}+a_{n-2}$. Now if $ \frac{a_{n-1}}{3} \ge (a_{n-1},a_n)> a_{n-2}$ then we are done since $ a_n>a_{n-1}+a_{n-2} \ge 4a_{n-2} \ge 2^n$. Otherwise $ \frac{a_{n-1}}{2}=(a_n,a_{n-1})$. Now if $ a_n \ge 2a_{n-1}$ we are done, otherwise it means that $ 2 \mid a_{n-1}$, $ 3 \nmid a_{n-1}$ and $ a_n=\frac{3}{2}a_{n-1}$. Now if $ \frac{a_{n-1}}{4} \ge a_{n-2} \implies a_n>a_{n-1} \ge 2^n$, in the last last case (since $ 3 \nmid a_{n-1}$) we must have $ (a_{n-2},a_{n-1})=\frac{a_{n-1}}{2}$, but $ \frac{a_{n-1}}{2}=(a_n,a_{n-1})>a_{n-2}=\frac{a_{n-1}}{2}$, contradiction.
Original thread: qui (c'è anche una soluzione che usa un'altra strada se non ricordo male)
Proposed by Morteza Saghafian, Iran, IMO Shortlist 2008
The only goal of science is the honor of the human spirit.

Rispondi