# Show that $\gcd(a_{n+1},a_n) > a_{n-1}$ implies $a_n \geq 2^n$

Let $(a_{n})$ be an infinite sequence of positive integers such that $\gcd(a_{n+1},a_{n}) > a_{n-1}$ for all $n\geq 1$. How do I prove that $a_{n} \geq 2^{n}$?

-
When prooving things with integers induction is always a hot candidate. Don't forget that you have to check $n=1$ and $n=2$ as an induction basis. –  Listing May 12 '11 at 18:48
This seems very hard. Every sequence of the form $a_n = r^n$ is valid, and it is possible to "interpolate" between them (i.e. a sequence can start as powers of 2 and later become powers of 3). –  quanta May 12 '11 at 22:23
@quanta: No, it cannot switch from powers of 2 to powers of 3, because if the last power of 2 is $a_n$, then $\gcd(a_{n+1},a_n)=1\lt a_{n-1}$. –  Arturo Magidin May 13 '11 at 3:32
It's possible to prove that $\frac{a_{n}}{\gcd(a_{n+1},a_n)}>1$? –  leo May 13 '11 at 4:01
@leo No because this is wrong for the sequence $2^n$. –  Phira May 13 '11 at 6:59

This question has four deleted answers by people who usually know what they're doing, so I might be stepping into a minefield here, but I think this is a valid proof:

First, note that the sequence has to be strictly increasing, since $a_n\ge \gcd(a_{n+1},a_n)>a_{n-1}$.

Now consider two successive terms $a_{n-1}$ and $a_n$ that differ by a factor of two or less: $a_n\le2a_{n-1}$. Then $\gcd(a_{n+1},a_n)=a_n$, since this has to be $a_n$ divided by an integer and $a_n$ divided by $2$ is already too small. Thus, in this case $a_{n+1}$ is a multiple of $a_n$. If $a_{n+1}=2a_n$, the same argument applies to $n+1$, and so on, either to infinity or until we encounter at least a three-fold multiple.

Thus, the sequence of ratios $a_{n+1}/a_n$ exhibits the following pattern: Every ratio less than or equal to $2$ may be followed by a string of $2$s; if this ends, it is followed by an integer greater than $2$; then there may follow further ratios greater than $2$ (not necessarily integers), to infinity or until we encounter the next ratio less than or equal to $2$, and then the pattern repeats.

This suggests an induction over sections of ratios, each beginning with an integer ratio, containing an integer ratio greater than $2$ and ending in a ratio less than or equal to $2$. If the inequality $a_n \geq 2^n$ ever fails, it will necessarily have to fail at the start of one of these sections. Thus, if we can show that it holds at the start of the first such section and that the product of the ratios in each section amounts at least to the corresponding number of factors of $2$, it will follow that the inequality holds for all $n$. (If there is a last "section" that goes to infinity without ever ending in a ratio less than or equal to $2$, that can't break the inequality.)

To get the induction off the ground, consider the two cases $a_0=1$ and $a_0\neq1$. (I'm assuming the indices start at $0$, since the conditions refer to $a_{n-1}$ for $n=1$.) If $a_0=1$, the first ratio is already an integer, so the first section starts right away and the inequality is satisfied, since $a_0=1\ge2^0$. If $a_0\neq1$, then $a_0\ge2=2^1$, so we're one factor of $2$ "ahead"; subsequent ratios greater than $2$ will preserve this excess, and the first ratio less than or equal to $2$ can't fully use it up since that ratio must be greater than $1$; thus in this case, too, the inequality will be satisfied at the start of the first section.

Now for each section we want to show that the product of the ratios in that section amounts at least to as many factors of $2$. This will necessarily be the case if in multiplying all the ratios except for the low ratio at the end of the section we accumulate at least an excess factor of $2$, since the low ratio must be greater than $1$.

We can ignore any ratios of $2$ at the beginning of the section, since they don't change the balance. Then we encounter an integer ratio greater than $2$. If this is greater or equal to $4$, we're done, since we then already have the required excess factor of $2$. So the only interesting case is a ratio of $3$.

So assume the first ratio in the section after any initial twos is $a_{k+1}/a_k=3$. That already gives us an excess factor of $\frac{3}{2}$. Now $\gcd(a_{k+2},a_{k+1})$ must be a divisor of $a_{k+1}$ and must be greater than $a_k$. Thus it can only be $a_{k+1}$ or $a_{k+1}/2$ (since $a_{k+1}/3=a_k$). If it is $a_{k+1}$, we're back to an integer ratio and will (possibly after some twos) encounter another integer ratio of at least $3$, taking the excess to at least $\frac{3}{2}\cdot\frac{3}{2}=\frac{9}{4}>2$. Thus the only case that could cause a problem is $\gcd(a_{k+2},a_{k+1})=a_{k+1}/2$.

Now consider the possible factors $r$ in $a_{k+2}=ra_{k+1}/2$. We must have $r\ge3$ since the sequence is strictly increasing. If $r=3$ or $r=4$, the ratio is $\frac{3}{2}$ or $2$ and thus ends the section without exhausting our accumulated excess of $\frac{3}{2}$, so this case is OK. If $r\ge6$, the ratio $a_{k+2}/a_{k+1}$ is at least $3$, giving us another excess factor of $\frac{3}{2}$ and taking us to $\frac{9}{4}>2$, so in that case we're also done. So the only case that could cause a problem is $r=5$, corresponding to a ratio of $\frac{5}{2}$. This gives us another excess factor of $\frac{5}{4}$.

But now the same arguments apply (with the ratio of $3$ replaced by $\frac{5}{2}$), so again we only have the options of going back to an integer ratio, ending the section with sufficient excess, taking the excess beyond $2$ or choosing $r=5$ for yet another ratio of $\frac{5}{2}$, which takes us back to the same situation. Eventually (in fact in just one more step), the excess factors of $\frac{5}{4}$ take the excess beyond $2$, and we're done.

Thus, every section necessarily accumulates an excess factor of $2$ that makes up for the low ratio at its end, so the inequality can never be violated.

-