IMO ShortList 2008, Number Theory problem 3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

13 users

TOPICS

No tags match your search

M

No tags match your search

M

IMO ShortList 2008, Number Theory problem 3

G H J

Reveal topic tags

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 2008, Number Theory problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1270 posts

April

#1 h Jul 9, 2009, 10:27 PM • 5 Y

Y by Davi-8191, anantmudgal09, Adventure10, Mango247, kiyoras_2001

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

925 posts

#2 h Jul 10, 2009, 6:12 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

mr bui

#3 h Jul 11, 2009, 4:52 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

469 posts

bboypa

#5 h Jul 13, 2009, 2:17 AM • 4 Y

Y by liimr, rtsiamis, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

34 posts

liimr

#6 h Jul 6, 2013, 7:24 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#7 h Apr 26, 2014, 3:18 AM • 4 Y

Y by mathocean97, HolyMath, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#9 h Feb 12, 2016, 4:12 AM • 2 Y

Y by Adventure10, Mango247

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 .

This post has been edited 1 time. Last edited by xdiegolazarox, Feb 12, 2016, 4:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

238 posts

#10 h Mar 29, 2016, 3:59 PM • 1 Y

Y by Adventure10

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

This post has been edited 1 time. Last edited by Stranger8, Sep 26, 2016, 1:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#11 h Apr 11, 2017, 1:20 AM • 2 Y

Y by Anar24, Adventure10

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3645 posts

cip999

#12 h Jun 18, 2017, 9:24 PM • 32 Y

Y by Anar24, nmd27082001, rmtf1111, anantmudgal09, Naysh, Arc_archer, pavel kozlov, toto1234567890, Phie11, MathbugAOPS, JasperL, MNJ2357, HolyMath, Supercali, MarkBcc168, rashah76, XbenX, parola, Elyson, Mathematicsislovely, guptaamitu1, Wizard0001, tapir1729, VicKmath7, Infinityfun, Adventure10, Mango247, math_comb01, SerdarBozdag, IMUKAT, puffypundo, megarnie

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1980 posts

#13 h May 30, 2018, 11:56 PM • 3 Y

Y by Saikat002, Adventure10, Mango247

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

Rik786

#15 h May 31, 2018, 8:27 AM • 3 Y

Y by cip999, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mastermind.hk16

143 posts

mastermind.hk16

#17 h Aug 4, 2019, 3:45 AM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 3 times. Last edited by mastermind.hk16, Aug 4, 2019, 4:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

820 posts

#18 h Sep 13, 2019, 3:55 PM • 1 Y

Y by Adventure10

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6874 posts

#19 h Nov 14, 2019, 8:52 PM • 5 Y

Y by WindTheorist, v4913, Adventure10, Mango247, MS_asdfgzxcvb

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#20 h Jan 21, 2020, 7:16 AM • 1 Y

Y by Adventure10

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 and $\beta=5$ . Then, $\gcd(a,5d)>2d$ , so $\gcd(a,5d)\in\{5d,5d/2\}$ . Thus, and so either 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 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 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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

452 posts

aops29

#21 h Jan 31, 2020, 2:40 PM • 2 Y

Y by AlastorMoody, Adventure10

Solution to 2008 N3

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1698 posts

awesomeming327.

#22 h Apr 11, 2023, 1:31 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5587 posts

#23 h Feb 3, 2024, 7:16 PM

Y by

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$ .

This post has been edited 1 time. Last edited by megarnie, Feb 3, 2024, 7:17 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#24 h May 23, 2024, 7:25 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1350 posts

i3435

#25 h Jul 8, 2024, 1:15 PM

Y by

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.

This post has been edited 1 time. Last edited by i3435, Jul 8, 2024, 1:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

120 posts

#26 h Jul 24, 2024, 9:46 PM

Y by

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.

This post has been edited 2 times. Last edited by lnzhonglp, Jul 24, 2024, 9:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1247 posts

#27 h Feb 2, 2025, 5:23 PM

Y by

awesomeming327. wrote:

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.

How does $a_{n+3} = a_{n+2}$ follow? I think this very direct induction approach (similarly to some other posts) does not work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

263 posts

L13832

#29 h Apr 6, 2025, 4:37 PM

Y by

got deleted by mistake ig

solution

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a