# Big-O notation: Prove that $3^x$ is $O(3^x - 2^x)$

I have to show that $$3^x$$ is $$O(3^x - 2^x)$$. I'm just starting to learn the basics of Big-Oh notation. I'm thinking you have to take logarithms here, but am stuck on how to show this is true once I get $$log(3^x-2^x)$$ (although it makes intuitive sense to me that this is true). Would appreciate any help!

• – Lord Shark the Unknown Nov 1 '18 at 7:01
• Consider $$\frac{3^x}{3^x-2^x}.$$ – Lord Shark the Unknown Nov 1 '18 at 7:01
• What is that limit? – Lord Shark the Unknown Nov 1 '18 at 7:05
• How would I compute that limit? Taking the log of the numerator and denominator, I get $xlog(3)$ in the numerator but don't know what to do with $log(3^x-2^x)$ in the denominator. – bob Nov 1 '18 at 7:06
• @bob You don't have to find the limit (there doesn't even have to be a limit for big-$O$ to make sense). You just have to show that that that fraction is (for large enough $x$) bounded both below and above by positive numbers. – Arthur Nov 1 '18 at 7:07

Consider the fraction $$\frac{3^x}{3^x-2^x}$$. Clearly, for $$x>0$$, this fraction is larger than $$1$$ (the numerator is larger than the denominator), so it is bounded below. Not that this is actually necessary for $$3^x=O(3^x-2^x)$$.
For bounded above, which is necessary, consider $$x>1$$. Note that $$2^x<2\cdot 3^{x-1}$$. This gives $$\frac{3^x}{3^x-2^x}<\frac{3^x}{3^x-2\cdot 3^{x-1}}=\frac3{3-2}$$ So the fraction is bounded above, and we're done.