April wrote: 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$. I use $ (a;b)$ as $ gcd(a;b)$. I prove this nice problem by induction. It is obvious to see that $ a_n > a_{n - 1}\forall n\in N$ Firstly, $ a_0\ge 1$. Let $ (a_1;a_2) = d > a_0\ge 2$. Thus $ a_1\ge 2$, $ a_2 = kd \ge 4$ because $ k\ge 2$. Suppose that this problem has been right until $ n - 1$. It means $ a_i\ge 2^i \forall i\le n - 1$. Assume that $ 2^{n - 1}\le a_{n - 1} < a_n < 2^n$. Let $ (a_n;a_{n - 1}) = d > a_{n - 2}\ge 2^{n - 2}$ and $ a_n = kd < 2^n;k\ge 2$. Because $ d\ge 2^{n - 2}$, if $ k\ge 4$ then $ a_n = kd\ge 2^n$ contr.It implies $ k = 2$ or $ k = 3$. Case I: $ k = 2$ then $ a_{n - 1} = d\ge 2^{n - 1}$(induction hypothesis) and $ a_n = 2d\ge 2^n$ which is contradiction !. Case II: $ k = 3$ then if $ a_{n - 1} = d$ by the same argument above, we have the contradiction . It means $ a_n = 3d;a_{n - 1} = 2d$.Let $ (a_{n - 2};2d) = T > a_n - 3\ge 2^{n - 3}$. Hence $ 2d = aT,a\ge 2$ $ a\ge 2$ implies $ T < 2^{n - 1}$(since $ 2^{n - 1}\le 2d = aT < 2^n$). If $ a\ge 4$ then $ aT\ge 2^{n - 1}$.It is impossible. Then $ a = 2$ or $ a = 3$. Case1: $ a = 2$ then $ d = T$ then $ a_{n - 2} = T\ge 2^{n - 2}$ then $ d\ge 2^{n - 1}$. Impossible!. Case 2: $ k = 3$. If $ a_{n - 2} = T$ then $ a_{n - 1} = 3T\ge 3.2^{n - 2}$ then $ a_n = 1,5 a_{n - 1}\ge 4,5.2^{n - 2} > 2^n$ contradiction. It means $ 2d = 3T$ and $ a_{n - 2} = 2T$ . Thus $ d = 1,5T < a_{n - 2}$. But $ (a_n;a_{n - 1}) = d > a_{n - 2}$ since initial hypothesis. So that assumption is wrong then $ a_n\ge 2^n$. I hope I don't make any stupid mistakes.

Sorry sir!!!! But we have a sequence isn't satisfy above condition: $ a_0=1,a_1=2,a_2=6,a_3=6$, but $ a_3<2^3=8$..... I thinks we have other condition in this problem.

April wrote: 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.

bboypa wrote: 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. this part i think has problem

It is a pity that there are no correct solutions here. Here is my solution. Basically I used $3^2 \textgreater 2^3$, and other similar inequalities. We use induction. Trivially $a$ is increasing, and we can check by hand that $a_i \ge 2^i$ for $i \le 4$. Now assume $a_m \ge 2^m$ for $i \le n$, and assume $a_{n+1} \textless 2^{n+1}$. If $a_n | a_{n+1}$ we achieve a contradiction since $a_{n+1} \ge 2a_n$. Therefore $a_n$ doesn't divide $a_{n+1}$. Let $d=(a_n, a_{n+1}) \textgreater a_{n-1}$. If $a_{n+1} \ge 4d$ we're done, and if $a_{n+1} \le 2d$ then $a_n | a_{n+1}$. Therefore $a_{n+1}=3d$ and so $a_n=2d$. Let $e=(2d,a_{n-1}) \textgreater a_{n-2} \ge 2^{n-2}$. Recall $d \textgreater a_{n-1}$. If $a_{n-1} | 2d$ then $a_{n-1} \le \frac{2d}{3}$ we see $3d \ge 9(2^{n-2})$ so we're done. So we get $a_{n-1} \neq e$, so $a_{n-1} \ge 2e$. But if $a_{n-1} \ge 3e$ then $3d \textgreater 3a_{n-1} \ge 9e \textgreater 9a_{n-2} \ge 9(2^{n-2})$ so we're done. From this we get $a_{n-1}=2e$ and so $e \ge 2^{n-2}$. If $2d \ge 6e$ then $3d \ge 9e \ge 9(2^{n-2})$ so we're done. Therefore $3e \le 2d \le 5e$. Since $d=(a_{n+1},a_n) \textgreater a_{n-1}=2e$ we get $2d \ge 4e$. Therefore $2d=5e$. So we can write $a_{n+1}=15f$, $a_n=10f$, $a_{n-1}=4f$. Let $X = a_{n-2} \textless (a_n, a_{n-1})=2f$. Redefine $d$ so that $d=(a_{n-1},a_{n-2}) \textgreater a_{n-3} \ge 2^{n-3}$. Let $T=4f/d$. If $T \ge 5$ then $4f \ge 5d \ge 5(2^{n-3})$ and so $2^{n+1} \textgreater 15f \ge 5d(15/4) \ge 2^{n-3}(75/4) \textgreater 2^{n+1}$, contradiction. Since $X \textless 2f$ then $d \textless 2f$ and so $T \ge 3$. So $d=f$ or $4f/3$ and $d | X\le 2f$ and so we see $X=d$. So $d \ge 2^{n-2}$ and from this, $4f = Td \ge 3d \ge 3(2^{n-2})$ and so $15f \ge 3(2^{n-2})(\frac{15}{4}) \textgreater 2^{n+1}$ so we're done. Such an ugly problem

My solution : It is obvious to see that $ a_n > a_{n - 1}\forall n\in N$.It is easy to see that true for $n = 0$,$1$,$2$,$3$,$4$. Now suppose that is true for $n = 0$,$1$,$2$ ... $k$ , $ k\ge 4$ .We assume that $ a_{k+1}<2^{k + 1}$ ,then it is easy to see that $ a_{k+1}< {2a_{k},4a_{k-1}}$, also $a_{k-1} < (a_{k}; a_{k+1}) \mid a_{k+1} - a_{k}$, also $a_{k} = p(a_{k}; a_{k+1})$ , then $4a_{k-1} >a_{k+1} \ge (p+1) (a_{k}; a_{k+1})> (p+1) (a_{k-1})$, then $ p \le 2$, but $p=1$ implies that $a_{k+1} \ge 2 a_{k}$ (contradiction) , then $p=2$ and $2a_{k+1}=3a_{k}$, in particular $a_{k+1}=3R$ and $a_{k}=2R$ , $R= (a_{k}; a_{k+1})$, but $ a_{k+1}<4a_{k-1} \implies a_{k-1} >\frac{3}{4}R$ , also $a_{k-1}<R$ ,let $Q= (a_{k}; a_{k-1}) \implies 2^{k-2}<Q=\frac{a_{k}-a_{k-1}}{X} < \frac{5R}{4X} \implies 2^{k+1}>3R>\frac{2^{k}3X}{5} \implies X\le3$ ,but $ R > a_{k-1}\ge Q=\frac{a_{k}-a_{k-1}}{X} \implies R>\frac{a_{k}}{X+1} = \frac{2R}{X+1} \implies X\ge2$ , but $X=2 \implies Q=\frac{a_{k}-a_{k-1}}{2} < \frac{a_{k}}{2} $ and $ a_{k-1}<R=\frac{a_{k}}{2} \implies \frac{a_{k}-a_{k-1}}{2} > \frac{a_{k}}{4} \implies \frac{a_{k}}{3}=\frac{a_{k}-a_{k-1}}{2} \implies \frac{3}{4}R<a_{k-1}=\frac{a_{k}}{3}=\frac{2R}{3}$ (contradiction), then $X=3$ ,also $Q=\frac{2R-a_{k-1}}{3} > \frac{2R}{6}$ and $a_{k-1} >\frac{3}{4}R>\frac{R}{2} \implies Q=\frac{2R-a_{k-1}}{3}< \frac{2R}{4} \implies Q=\frac{2R}{5}\implies a_{k-1}=\frac{4R}{5}$ ,let $T=(a_{k-1}; a_{k-2})=\frac{a_{k-2}}{Y} \implies\frac{2(2^{k+1})}{15}>\frac{2R}{5}>a_{k-2}>Y(a_{k-3})>Y(2^{k-3}) \implies 32>15Y \implies Y\le2$ ,but $Y=1 \implies T=a_{k-2} \implies a_{k-2}\mid \frac{4R}{5}$ and $a_{k-2}<\frac{2R}{5} \implies 2^{k-2}< a_{k-2} \le \frac{4R}{15}< \frac{4(2^{k+1})}{45} $ (contradiction),then $Y=2 \implies \frac{a_{k-2}}{2} \mid \frac{4R}{5} \implies a_{k-2} \mid \frac{8R}{5}$,but $ a_{k-2}\textless \frac{2R}{5}=\frac{8R}{(4)5} \implies 2^{k-2}\textless a_{k-2}\le \frac{8R}{25}\textless \frac{8(2^{k+1})}{75}$ (contradiction) ,then $a_{k+1}\ge 2^{k + 1}$ ,with what would be complete induction .

mr bui wrote: Sorry sir!!!! But we have a sequence isn't satisfy above condition: $ a_0=1,a_1=2,a_2=6,a_3=6$, but $ a_3<2^3=8$..... I thinks we have other condition in this problem. All terms in this sequence satisfy this condition not part of them ,directly you won't find an integer $a_4$ that satisfies this condition following your sequence

I think this problem deserves more than it seems, so here's a proof not going through some dreadful induction and massive casework. First, let $\frac{a_{n + 1}}{a_n} = \frac{x_n}{y_n}$, where $x_n$, $y_n$ are positive integers and $(x_n, \: y_n) = 1$. Then we get $$(a_{n + 1}, \: a_{n + 2}) = \frac{a_{n + 1}}{y_{n + 1}} > a_n \implies y_{n + 1} < \frac{a_{n + 1}}{a_n} = \frac{x_n}{y_n} \implies \frac{x_n}{y_n} \ge y_{n + 1} + \frac{1}{y_n}$$Now observe that $$a_n = a_0 \cdot \frac{a_1}{a_0} \cdots \frac{a_n}{a_{n - 1}} = a_0 \cdot \frac{x_0}{y_0} \cdots \frac{x_{n - 1}}{y_{n - 1}} \ge a_0\left(y_1 + \frac{1}{y_0}\right)\cdots\left(y_n + \frac{1}{y_{n - 1}}\right)$$By AM-GM $y_{i + 1} + \frac{1}{y_i} \ge 2\sqrt{\frac{y_{i + 1}}{y_i}}$; furthermore, since $a_1 = \frac{x_0}{y_0}a_0$, $y_0 \mid a_0 \implies a_0 \ge y_0$. Thus we have $$a_n \ge a_0\left(y_1 + \frac{1}{y_0}\right)\cdots\left(y_n + \frac{1}{y_{n - 1}}\right) \ge y_0\left(2\sqrt{\frac{y_1}{y_0}}\right)\cdots\left(2\sqrt{\frac{y_n}{y_{n - 1}}}\right) = 2^n\sqrt{y_0y_n} \ge 2^n$$which ends the proof.

I'm writing this late at night so please let me know if you spot any errors April wrote: 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$. Proposed by Morteza Saghafian, Iran Note that $a_k \ge (a_k,a_{k+1})>a_{k-1}$ for all $k>0$. Note $a_0 \ge 1$ and $a_1>a_0\ge 1$ hence $a_1 \ge 2$. Now if $a_2=3$ then $(a_2,a_1)=1$; false! So $a_2 \ge 4$. Now pick the minimal $k>1$ with $a_{k+1}<2^{k+1}$. Then $2^k \le a_k<a_{k+1}<2^{k+1}$ and $k>1$ and $(a_{k+1}, a_k)>a_{k-1} \ge 2^{k-1}$. Notice that $a_k \nmid a_{k+1}$ hence $(a_{k+1}, a_k) \le \frac{a_k}{2}$ so $a_k> 2a_{k-1}$. Also $a_{k+1}-a_k \ge (a_{k+1}, a_k)>2^{k-1}$ hence $a_k<3 \cdot 2^{k-1}$. Now if $(a_{k-1}, a_k) \ne a_k-2a_{k-1}$ then $(a_{k-1}, a_k)\le \frac{a_k-2a_{k-1}}{2} \le \frac{2^{k-1}}{2}<a_{k-2}$ a contradiction! Hence $a_k=n_1(a_k-2a_{k-1})$ for some integer $n_1>1$. Then $a_k=\frac{2n_1}{n_1-1}a_{k-1}$ and $a_k<3a_{k-1} \implies n_1>3$. Now $(a_{k-1}, a_k)=\frac{a_{k-1}}{n_1-1}$ if $n_1-1$ is odd else $(a_{k-1}, a_k)=\frac{2a_{k-1}}{n_1-1}$ if $n_1-1$ is even. Either way, $a_{k-1}>2a_{k-2}$. Now $a_k<3 \cdot 2^{k-1} \implies a_{k-1}<3 \cdot 2^{k-2}$ and $2a_{k-2}<a_{k-1}<3a_{k-2}$. Thus, applying the previous argument again, we can find $n_2$ with $a_{k-1}=\frac{2n_2}{n_2-1}a_{k-2}$. Note that this procedure can be continued to obtain integers $n_3, \dots, n_{k-1}>3$ with similar relations; so $$3 \cdot 2^{j-1}>a_j=2^{j-1}\cdot \left(\frac{n_1 \cdot \dots \cdot n_{j-1}}{(n_1-1)\cdot \dots \cdot (n_{j-1}-1)}\right) \cdot a_1$$and $a_j$ is an integer for all $j \le k$. Thus, $a_1=2$ and $a_2=\frac{2n_{k-1}}{n_{k-1}-1}a_1$ is an integer so $a_2=5$ and so $5 \mid a_3$ but $a_3=\frac{2n_{k-2}}{n_{k-2}-1}a_2$ hence $a_3=11$ or $a_3=12$; contradiction!

cip999 wrote: I think this problem deserves more than it seems, so here's a proof not going through some dreadful induction and massive casework. First, let $\frac{a_{n + 1}}{a_n} = \frac{x_n}{y_n}$, where $x_n$, $y_n$ are positive integers and $(x_n, \: y_n) = 1$. Then we get $$(a_{n + 1}, \: a_{n + 2}) = \frac{a_{n + 1}}{y_{n + 1}} > a_n \implies y_{n + 1} < \frac{a_{n + 1}}{a_n} = \frac{x_n}{y_n} \implies \frac{x_n}{y_n} \ge y_{n + 1} + \frac{1}{y_n}$$Now observe that $$a_n = a_0 \cdot \frac{a_1}{a_0} \cdots \frac{a_n}{a_{n - 1}} = a_0 \cdot \frac{x_0}{y_0} \cdots \frac{x_{n - 1}}{y_{n - 1}} \ge a_0\left(y_1 + \frac{1}{y_0}\right)\cdots\left(y_n + \frac{1}{y_{n - 1}}\right)$$By AM-GM $y_{i + 1} + \frac{1}{y_i} \ge 2\sqrt{\frac{y_{i + 1}}{y_i}}$; furthermore, since $a_1 = \frac{x_0}{y_0}a_0$, $y_0 \mid a_0 \implies a_0 \ge y_0$. Thus we have $$a_n \ge a_0\left(y_1 + \frac{1}{y_0}\right)\cdots\left(y_n + \frac{1}{y_{n - 1}}\right) \ge y_0\left(2\sqrt{\frac{y_1}{y_0}}\right)\cdots\left(2\sqrt{\frac{y_n}{y_{n - 1}}}\right) = 2^n\sqrt{y_0y_n} \ge 2^n$$which ends the proof. Done a very good job and innovative

First, note that $ a_i \geq (a_i, a_{i+1}) > a_{i-1}$. Let us prove the result by strong induction on $n$. Base case: $n=0,1,2,3$ Clearly, $a_0 \geq 1$ and $a_1 \geq 2$ because $a_1>a_0$. $(a_2,a_1) \geq 2 \longrightarrow a_2 \geq a_1 +2 \geq 4$. $(a_3,a_2) \geq 3 \longrightarrow a_3 \geq a_2 +3 \geq 7$. But if $a_3 =7$, then $(a_3,a_2)=1$. Contradiction. So $a_3 \geq 8$. Assume for all $i \leq n, \ a_i \geq 2_i$. Consider $a_{n+1}$. We have $a_{n+1} \geq (a_{n+2},a_{n+1})> a_n$. Also, $d=(a_{n+1},a_{n}) > 2^{n-1}$ by the induction hypothesis. Let $d = \frac{a_n}{m}$ and assume $m \geq 3$. Since $d \mid a_{n+1},$ Then $a_{n+1} \geq d(m+1) \geq \frac{a_n}{m} (m+1) > (m+1) \cdot 2^{n-1} \geq 4 \cdot 2^{n-1}=2^{n+1}$ So now $m=1$. Then $a_{n+1} > a_n =d \Longrightarrow a_{n+1} \geq 2a_n \geq 2^{n+1}$. Lastly, $m=2$. Then $a_{n+1} \geq \frac{3}{2} a_n$. Write $a_i = 2^i + b_i \ \ \forall i \leq n, \ (b_i \geq 0)$ Since $d = \frac{a_n}{2} > a_{n-1} \longrightarrow b_n > 2b_{n-1}$. If $b_n \geq 2^{n-1}$, then $a_{n+1} \geq 3(2^{n-1} +2^{n-2}) > 2^{n+1}$. The last inequality simplifies to $9>8$. So now assume $b_n < 2^{n-1} \dots (*)$ Consider $e=(a_n, a_{n-1})$ and $f=(a_{n-1}, a_{n-2})$. If $e=a_{n-1}$, then $a_{n-1} \mid a_n \Longleftrightarrow a_{n-1} \mid b_n -2b_{n-1}$. But $0 < b_n -2b_{n-1} < 2^{n-1} \leq a_{n-1} \leq b_n -2b_{n-1}$. Contradiction. So $ a_{n-2}<e \leq \frac{a_{n-1}}{2} \longrightarrow b_{n-1}-2b_{n-2}>0$. Also $$2^{n-2}<e = (b_n -2b_{n-1}, a_{n-1}) \leq b_n -2b_{n-1}$$Hence $a_n =2^n +b_n > 2^n +2^{n-2} + 2b_{n-1}$. If $b_{n-1} \geq 2^{n-3}$, we are done from $(*)$. So assume $b_{n-1} < 2^{n-3}$. Repeating the same argument as before we get that $f \leq \frac{a_{n-2}}{2}$. But $$2^{n-3}<f = (b_{n-1}-2b_{n-2}, a_{n-2}) \leq b_{n-1} -2b_{n-2} \leq b_{n-1}$$This is a contradiction. And our induction is complete.

Yay, we're back yet again with another keep-bashing-mindlessly-until-you-get-something problem! Looking at the problem, there's nothing which immediately strikes as obviously helping to solve the problem, and the condition really calls for an inductive argument, so here we have it- First let's observe, quite obviously, that the sequence is a strictly increasing one, as $a_i \geq gcd(a_i,a_{i+1})>a_{i-1}$. Now, assume for all $i \in [1,2,3,...,i-1]$, $a_i \geq 2^i$ (strong inductive argument). For the sake of contradiction, also assume that $a_i<2^i =>$ write $a_i=2^{i-1}+k, k<2^{i-1}$. As $gcd(a_i,a_{i-1})>a_2$, and by assumption, write $a_{i-1}=2^{i-1}+l, l<2^{i-1} =>gcd(2^{i-1}+k,2^{i-1}+l)>2^{i-2}$ $=>gcd(k,2^{i-1}+l-k)>2^{i-2}=>k \mid 2^{i-1}+l-k$ (using $k<2^{i-1}$) and $k>2^{i-2}$ Hence $k \mid 2^{i-1}+l$. Writing $k=2^{i-2}+m$, we get $2^{i-2}+m \mid 2^{i-1}+l => 2^{i-2}+m \mid l-2m$. As $l<2^{i-1},m<2^{i-2}=>|l-2m| <2^{i-1}=> 2m-l =2^{i-2}+m (\neq$ possible as $=>m>2^{i-2}=>k>2^{i-1}$) or $l=3m+2^{i-2}$. When $l=3m+2^{i-2}$, we get $a_i=2^{i-1}+2^{i-2}+m$ and $a_{i-1}=2^{i-1}+2^{i-2}+3m$ - I was actually feeling a little despondent after getting this, thinking that I had done all of the above for nothing, until I realised it's a direct violation of monotonicity! $=>$ our assumption $a_i<2^i$ was indeed false. And thus, we've finally wrapped up all the possible cases, and all that's left to establish is the base case(s). Notice that $a_0$ is automatically $ \geq 1$, and if $a_1<2=>a_1=1$, then $gcd(a_1,a_2)=1>a_3$ couldn't possibly hold true. Finally, as $gcd(a_2,a_3)>2$, if $a_2<4=>a_2=3$, and this is only possible if $a_1=2$. But as this would imply $gcd(a_1,a_2)=1$, $gcd(a_1,a_2)>a_0$ couldn't possibly be true. As we only used $i,i-1,i-2$ in our argument, we're done!

Note $a_i \ge \gcd(a_i, a_{i+1}) > a_{i-1}$ so that the sequence is strictly increasing. Thus let $r_i = \frac{a_{i+1}}{a_i} > 1$ for each $i$. Let's rephrase the condition in terms of the $r_i$. Let $d_i$ denote the denominator of $r_i$ in lowest terms. Claim: We always have $r_i > d_{i+1}$. Proof. Extend $\gcd \colon {\mathbb Q}_{>0} \times {\mathbb Q}_{>0} \to {\mathbb Q}_{>0}$ by $\gcd(a,b) = \prod_p p^{\min(\nu_p(a), \nu_p(b))}$. Then the condition is $ \gcd(r_i a_i, r_i r_{i+1} a_i) > a_i \iff \frac{1}{d_{i+1}} = \gcd(1, r_{i+1}) > \frac{1}{r_i}$ as needed. $\blacksquare$ Let's say an index is critical if $r_i < 2$ and hence $d_i \ge 2$. Claim: If $i \ge 3$ is a critical index, there exists $e \le 3$ such that $r_{i-1}$, \dots, $r_{i-e}$ are not critical and $r_{i-e} \dots r_i > 2^{e+1}$. Proof. Choose a critical index $i$. We consider several cases. If $d_i \ge 3$ then $r_{i-1} > d_i$ and we have $r_{i-1} r_i > d_i \cdot \frac{d_i+1}{d_i} \ge 4 = 2^2. $ Suppose $d_i = 2$ and $d_{i-1} = 1$. Then $r_{i-1} r_i > 3 \cdot \frac 32 = \frac 92 > 2^2$. Suppose $d_i = 2$ and $d_{i-1} = 2$. There are two sub-cases. If $d_{i-2} = 1$ then $ r_{i-2} r_{i-1} r_i > 3 \cdot \frac 52 \cdot \frac 32 > 2^3. $ On the other hand if $d_{i-2} \ge 2$ then $ r_{i-3} r_{i-2} r_{i-1} r_i > d_{i-2} \cdot \frac{2d_{i-2}+1}{d_{i-2}} \cdot \frac 52 \cdot \frac 32 = \frac{15}{4}(2d_{i-2}+1) \ge \frac{75}{4} > 2^4. $ Suppose $d_i = 2$ but $d_{i-1} \ge 3$. Then $r_{i-2} > d_{i-1}$ and we have $ r_{i-2} r_{i-1} r_i > d_{i-1} \cdot \frac{2d_{i-1}+1}{d_{i-1}} \cdot \frac 32 = 7 \cdot \frac 32 > 2^3.$ This completes the proof. $\blacksquare$ Thus by induction it suffices to show $a_i \ge 2^i$ only for $i=0,1,2,3$, which is routine.

Note that \[a_i\ge \gcd(a_i,a_{i+1})>a_{i-1},\]so the sequence is strictly increasing. We'll be implicitly using this fact over and over in the proof. We prove the result by induction on $i$. We begin with the base case. Claim: [Induction Base Case] We have $a_i\ge 2^i$ for $i\in\{0,1,2\}$. Proof: We have $a_0\ge 1$, and $a_1>a_0\ge 1$, so $a_1\ge 2$. It suffices to show that $a_2\ge 4$. Note that $a_2\ge a_1+1$ and $a_1\ge 2$, so the only case in which $a_2\le 3$ is if $a_2=2$ and $a_3=3$. This doesn't work as $\gcd(a_2,a_3)=1\not>a_1$. $\blacksquare$ Before proving the inductive step, we have the following useful lemma. Lemma: If $a_i\le 2a_{i-1}$, then $a_i\mid a_{i+1}$. Proof: Note that $\gcd(a_i,a_{i+1})=a_i$ or $\gcd(a_i,a_{i+1})\le a_i/2\le a_{i-1}$. The latter case can't happen by the problem condition, so we have $\gcd(a_i,a_{i+1})=a_i$, or $a_i\mid a_{i+1}$. $\blacksquare$ Claim: [Inductive Step] Suppose $i\ge 2$. Then, if $a_j\ge 2^j$ for all $0\le j\le i$, then $a_{i+1}\ge 2^i$. Proof: Let $a_{i-2}=b$, $a_{i-1}=d\alpha$, $a_i=d\beta$, and $a_{i+1}=a$, where $\gcd(\alpha,\beta)=1$. The problem condition gives us $d>b$ and $\gcd(a,d\beta)>d\alpha$. Furthermore, we know that $b\ge 2^{i-2}$, $d\alpha\ge 2^{i-1}$, and $d\beta\ge 2^i$. Our goal is to show that $a\ge 2^{i+1}$. We have the following cases. Case 1: Suppose $\beta\ge 8$. Then, \[a>d\beta\ge 8d>8b\ge 8\cdot 2^{i-2}= 2^{i+1},\]as desired. Case 2: Suppose $\beta\le 7$ and $\beta\le 2\alpha$. Then, we have $d\beta\le 2(d\alpha)$, so by the lemma, we have $d\beta\mid a$. We also know that $a>d\beta$, so we have \[a\ge 2d\beta\ge 2\cdot 2^i=2^{i+1},\]as desired. Case 3: Suppose $\beta\le 7$ and $\beta\ge 4\alpha$. Then, we have \[a>d\beta\ge 4d\alpha\ge 4\cdot 2^{i-1}=2^{i+1},\]as desired. Case 4: Suppose $\beta\le 7$ and $2\alpha<\beta<4\alpha$. Since $\gcd(\alpha,\beta)=1$, we have the following subcases. Case 4.1: Suppose $\alpha=1$ and $\beta=3$. Then, $\gcd(a,3d)>d$, so we have $\gcd(a,3d)\in\{3d,3d/2\}$. Thus, $\tfrac{3d}{2}\mid a$ and $a>3d$, so \[a\ge\frac{9d}{2}>4d=4d\alpha\ge 4\cdot 2^{i-1}=2^{i+1},\]as desired. Case 4.2: Suppose $\alpha=2$ and $\beta=5$. Then, $\gcd(a,5d)>2d$, so $\gcd(a,5d)\in\{5d,5d/2\}$. Thus, $\tfrac{5d}{2}\mid a$ and $a>5d$ so either \[a\ge 10d=2\cdot(d\beta)\ge 2\cdot 2^i=2^{i+1},\]or $a=\tfrac{15d}{2}$. So it suffices to look at the case where $a_{i-2}=b$, $a_{i-1}=2d$, $a_i=5d$, $a_{i+1}=\tfrac{15d}{2}$. In this case, we have $d$ even, so $a_{i+1}\ge 15$. So we're already done if $i=2$, so we may assume $i\ge 3$. Because of this, we may define $c=a_{i-3}$, noting that $c\ge 2^{i-3}$. Recall that in this case, our sequence contains \[c,b,2d,5d,\frac{15d}{2}\]as a subsequence. We have the following two subcases. Case 4.2.1: Suppose $b>2c$. Then, $\gcd(2d,b)>c$ so $\gcd(b,2(d-b))>c$. Since $d>b$, this implies that $2(d-b)>c$, so $2d>2b+c>5c$. Thus, \[a=\frac{15d}{2}>\frac{15}{4}\cdot 5c\ge \frac{75}{4}\cdot 2^{i-3}>2^{i+1},\]as desired. Case 4.2.3: Suppose $b\le 2c$. By the lemma, we have that $b\mid 2d$ and $d>b$, so $2d\ge 3b$. Thus, \[a=\frac{15d}{2}\ge\frac{15}{4}\cdot 3b\ge\frac{45}{4}\cdot 2^{i-2}\ge 2^{i+1},\]as desired. Case 4.4: Suppose $\alpha=2$ and $\beta=7$. Then, $\gcd(a,7d)\ge 2d$, so $\gcd(a,7d)\in\{7d,7d/2,7d/3\}$. Thus $a$ is a multiple of $7d/2$ or $7d/3$, and since $a>7d$, we have that \[a\ge \frac{4}{3}\cdot 7d\ge \frac{28}{3}\cdot 2^{i-2}\ge 2^{i+1},\]as desired. Case 4.4: Suppose $\alpha=3$ and $\beta=7$. Then, $\gcd(a,7d)\ge 2d$, so $\gcd(a,7d)\in\{7d,7d/2\}$. The proof then proceeds exactly as in the previous case. Thus, we've shown that $a\ge 2^{i+1}$ in all cases, proving the claim. $\blacksquare$ Combining the base case and the inductive step completes the proof.

We proceed with induction. It is easy to verify that $a_0\ge 1$ and $a_1\ge 2$. Suppose $a_n\ge 2^n$ and $a_{n+1}\ge 2^{n+1}$, then \begin{align*} \text{gcd}(a_{n+2}, a_{n+1}) &> a_n \\ \text{gcd}(a_{n+3}, a_{n+2}) &> a_{n+1} \end{align*}Let $a_{n+2}=k\text{gcd}(a_{n+2}, a_{n+1}) = l\text{gcd}(a_{n+3}, a_{n+2})$. If $k=1$ then $a_{n+2}\mid a_{n+1}$, impossible by the second one. If $k=2$ then $a_{n+2}=2a_{n+1}\ge 2^{n+2}$ as desired. If $k=3$ then either $a_{n+2}=3a_{n+1}$ which implies the result or \[a_{n+2}=\frac32 a_{n+1}\]but that'll imply $a_{n+3}=a_{n+2}$ which similarly to $a_{n+2}\mid a_{n+1}$ will not work. If $k=4$ then $a_{n+2}>4a_n\ge 2^{n+2}$ as desired.

Suppose this was false. Clearly this is true for $0$ (since $a_0 \ge 1 = 2^0$). Now let $n$ be the smallest nonnegative integer for which $a_{n+1} < 2^{n+1}$. This implies $a_i \ge 2^i$ for all $0\le i\le n$. First notice that the sequence must be strictly increasing. Let $d = \gcd(a_n, a_{n+1})$. We have $d > a_{n-1} \ge 2^{n-1}$, therefore $\frac{a_{n+1}}{d} < 4$. Now, this implies that both $\frac{a_n}{d}$ and $\frac{a_{n+1}}{d}$ are positive integers under $4$. If $a_n = d$, then $a_n \mid a_{n+1}$, but since $a_{n+1} > a_n$, we have $a_{n+1} \ge 2a_n \ge 2^{n+1}$, contradiction. Thus, $a_n = 2d$ and $a_{n+1} = 3d$ must hold and $d > a_{n-1}$. If $n = 1$, then $a_2 = 3d < 4$, so $d = 1$, absurd since $d > a_0$. Thus, $n > 1$. Therefore, we have $3d < 2^{n+1} \implies d < \frac{2^{n+1}}{3}$. Looking at $\gcd(a_{n-1}, a_n)$, we see $\gcd(a_{n-1}, 2d) > a_{n-2} \ge 2^{n-2}$. We have \[ \frac{a_{n-1}}{\gcd(a_{n-1}, 2d)} < \frac{a_{n-1}}{2^{n-2}} \le \frac{d}{2^{n-2}} \le \frac 83, \]so the fraction must be either $1$ or $2$. If it is $1$, then $a_{n-1} \mid 2d$. Now note that $2d < \frac{2^{n+2}}{3} \le a_{n-1} \cdot \frac{8}{3}$, meaning that either $a_{n-1} = 2d$ or $2a_{n-1} = 2d$, both contradict $a_{n-1} < d$. Hence we must have $\frac{a_{n-1}}{\gcd(a_{n-1}, 2d) } = 2$, so $\gcd(a_{n-1}, 2d) = \frac{a_{n-1}}{2}$. Now, let $2d = k \cdot \frac{a_{n-1}}{2}$. Since $a_{n-1} < d$, $k > 4$. We have $k \cdot 2^{n-2} \le k \cdot \frac{a_{n-1}}{2} < \frac{2^{n+2}}{3}$, so $k < \frac{16}{3}$. Thus, $k = 5$ must hold. Therefore $d$ is a multiple of $5$, so let $d = 5x$. We see that $a_{n-1} = 4x, a_n = 10x, a_{n+1} = 15x$. If $n = 2$ held, then $a_3 = 15x < 8$, which is impossible. Now we look at $\gcd(a_{n-2}, 4x)$. Call it $m$. It must be greater than $a_{n-3} \ge 2^{n-3}$. We have $\frac{2^{n-1}}{5} < x < \frac{2^{n+1}}{15}$. Notice that $\gcd(a_{n-1}, a_n) > a_{n -2}$, so $\gcd(4x, 10x) > a_{n-2}$ implying that $a_{n-2} < 2x$. We see that $ \frac{a_{n-2}}{m} < \frac{2x}{m} < \frac{2^{n+2}}{15 \cdot 2^{n-3}} < 3$, so $\frac{a_{n-2}}{m}$ must be either $1$ or $2$. Since $a_{n-2} > a_{n-3}$, we cannot have $a_{n-2} = m$, so we must have $a_{n-2} = 2m$. Thus, we must have $m < x$. Now, we have $\frac{4x}{m} > 4$, but \[ \frac{4x}{m} < \frac{4x}{2^{n-3}} < \frac{64}{15} < 5 ,\]so $\frac{4x}{m}$ is not an integer. Hence we have a contradiction, so $a_n \ge 2^n$ for all nonnegative integers $n$.

Note that $a_n> a_{n-1}$ since $\text{gcd} (a_n,a_{n+1})\le a_n$. I show that for $n\ge 3$, if $a_n<2a_{n-1},4a_{n-2},8a_{n-3}$ then $15\mid a_n$ and if $n\ge 4$ then $16a_{n-4}<a_n$. This will solve the problem because for $n=0$ $a_n\ge 1$, for $n=1$ $a_1>a_0$ so $a_1\ge 2$, for $n=2$ $a_2>a_1>a_0$ so either $a_2\ge 4$ or $a_2=3,a_2=2,a_2=1$ which is impossible for $n=3$ $a_3\ge 8$ or $15\mid a_3$ for $n\ge 4$ strong induction works. Suppose for $n\ge 3$ that $a_n<2a_{n-1},4a_{n-2},8a_{n-3}$. In what follows, we use the property that $\text{gcd}(a_i,a_{i+1})$ is less than the absolute value of any nonzero linear combination of $a_i$ and $a_{i+1}$. $a_n-a_{n-1}>a_{n-2}$, so $a_{n-1}\le \frac{3}{4} a_n$ since $a_{n-2}>\frac{1}{4}a_n$. $2a_{n-1}-a_n>a_{n-2}>\frac{a_n}{4}$ so $a_{n-1}>\frac{5}{8}a_n$. $\left|3a_{n-1}-2{a_n}\right|$ is either $0$ or greater than $\frac{a_n}{4}$, which is impossible unless $a_{n-1}=\frac{2}{3}a_n$. $a_{n-2}<a_n-a_{n-1}$ so $a_{n-2}<\frac{a_n}{3}$. $\frac{a_n}{8}<a_{n-3}<a_{n-1}-2a_{n-2}$ so $a_{n-2}<\frac{13}{48}a_n$. $\left|2a_{n-1}-5a_{n-2}\right|$ is either $0$ or greater than $\frac{a_n}{8}$, so it equals $0$ and $a_{n-2}=\frac{4}{15}a_n$. Thus $15\mid a_n$. If $n\ge 4$, then $a_{n-3}<a_{n-1}-2a_{n-2}$ so $a_{n-3}<\frac{2}{15}a_n$. $a_{n-4}<a_{n-2}-2a_{n-3}<\frac{a_n}{60}$, as desired.

We use strong induction on $n$. The base cases up to $n=2$ are easy to verify. It is easy to check that the sequence must be strictly increasing. Now suppose $a_n \geq 2^n$ for up to $n$, and let $\gcd(a_n, a_{n+1}) = m$ and $a_{n+1} = km > ka_{n-1}$. If $k \geq 4$, then $a_{n+1} \geq 4a_{n-1} \geq 2^{n+1}$ and we are done. If $k=3$, then we get $\gcd(a_n, 3m) = m > a_{n-1}$ and $a_n$ must be either $m$ or $2m$. Let $a_{n-1} = m-b$. If $a_n = m$, then $a_{n+1} = 3m \geq 3 \cdot 2^{n} > 2^{n+1}$. If $a_n = 2m$, then $$\frac 12 \gcd(2m, 2m-2b) = \gcd(m, m-b) = \gcd(m, b) \leq \gcd(2m, m-b) = \gcd(a_n, a_{n-1}) \leq a_{n-2} = 2^{n-2},$$so $b \geq 2^{n-2}$ and $m \geq 2^{n-2} + 2^{n-1}$, so $a_{n+1} = 3m \geq 2^{n+1} + 2^{n-2} > 2^{n+1}$, as desired. If $k = 2$, then $a_{n+1} \geq 2a_n \geq 2^{n+1}$ and we are done. We have checked all cases so the induction is complete.