9
$\begingroup$

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}$?

  • 7
    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.2011-05-12
  • 0
    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).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
  • 0
    It'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
  • 0
    Thank 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
  • 0
    If 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

1 Answers 1