Search code examples
big-odiscrete-mathematicsproof

Prove for any a > b >0, b^n in Big-O a^n

Prove that for any real numbers, a, b such that a > b > 0, b^n is O(a^n), n >=1.

I have searched several textbooks I own on Discrete Mathematics as well as several online searches for any examples that are similar or theorems that related to this proof. I am not looking for a direct solution, but perhaps being shown the right methods or paradigms to solve the proof.

Solution

  • If you mean

    Prove that for any real numbers, a, b such that a > b > 0, b^n is O(a^n)

    Then, think about the definition of O(a^n)

    From wiki,

    1) For f(x), g(x) defined on a subset of reals
2) if there exists some positive **constant** M and real number x_0, such that
3) if ABS(f(x)) <= M * ABS(g(x)) for all x > x_0

    In this case f(x) = b^x and g(x) = a^x. I'm going to treat this question as if it's a homework question, even though it isn't tagged as one...please correct me if I'm wrong!

    Consider plugging the funciton into the steps (especially 3) and see if you can figure out any x_0, M pair for which it is true. Good luck!

    EDIT I changed f(x) = b^n and g(x) = a^n to f(x) = b^x and g(x) = a^x

    EDIT - HINT

    Step 3) can be interpreted as:

    ABS(f(x)) / ABS(g(x)) <= M for all x > x_0

    Choose your favorite constant M and then see if you can find some x_0 which works for all x.