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}$?
Show that $\gcd(a_{n+1},a_n) > a_{n-1}$ implies $a_n \geq 2^n$
9
$\begingroup$
elementary-number-theory
-
7When 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. – 2011-05-12
-
0This 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). – 2011-05-12
-
0@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}$. – 2011-05-13
-
0It's possible to prove that $\frac{a_{n}}{\gcd(a_{n+1},a_n)}>1$? – 2011-05-13
-
0@leo No because this is wrong for the sequence $2^n$. – 2011-05-13
-
0@Arturo, `2^0,2^1,2^2,2^3,2^3*3,2^2*3^2,2^2*3^3,2^1*3^4,2^1*3^5,3^6,3^7,...` – 2011-05-13
-
0@leo, it is easy to show that $1 < a_{n+1}/\gcd(a_n,a_{n+1})$ (I will post proof if you want). That can prove that $2^n < a_{n+1}$ but does not prove the theorem. – 2011-05-13
-
0Thank you @ user9325. I did not see your comment before. – 2011-05-13
-
0@quanta: I wouldn't call that a switch, but fair enough. – 2011-05-13
-
0@Arturo, I call it interpolation. I could conjecture that every sequence satisfying the condition is just interpolations (they can probably mix together) between different pure power sequences.. but to conjecture this is useless because I can't prove it. – 2011-05-13
-
0If that were true then one could try to show that interpolating cannot drop you below $2^n$ (probably something much stronger than that holds). – 2011-05-13