# BIG-O proposed proof

I would like to prove that the statement $40^n = O(2^n)$ is false

Would the following suffice as a proof?

Let k be some arbitrary number. Let c = $\frac {40^k}{2^k}$. Then if n>k

$\frac {40^n}{2^n}=\frac {40^k}{2^k}*\frac {40^{n-k}}{2^{n-k}}$.

Then it follows that $\frac {40^{n-k}}{2^{n-k}}>1$ and so we are going uphill.

If n>k,

$\frac {40^n}{2^n}>\frac {40^k}{2^k}=c$

and so

${40^n} \not \lt c(2^n)$

-
If you want a "fancy" exponent, enclose it in braces. "40^n-k" produces $40^n-k$; but "40^{n-k}" gives $40^{n-k}$ (which is what you want here). – David Mitra Dec 15 '12 at 17:05

## 2 Answers

I think your attempt contains the right idea but it's a little bit messy!

The easiest way when you are asked to disprove something like this is to work by contradiction.

So assume $40^n=O(2^n)$ hence there exist $N$ and $k$ in $\mathbb{N}$ such that $\forall n > N$

$40^n\leq k\cdot 2^n$ hence $20^n\leq k$ but this is clearly a contradiction as $20^n \rightarrow \infty$ for $n\rightarrow \infty$

-

You've only shown that the statement

$\qquad\qquad\qquad\qquad$"$40^n< c2^n$ for $n$ sufficiently large"

is false for certain values of $c$ (namely, of the form $40^k/2^k$). So your proof is a bit off.

You need to show that the aforementioned statement is false for any value of $c$. Towards this end, you might first show that $\lim\limits_{k\rightarrow\infty}{40^k\over 2^k}=\infty$. (Then, given $c$, you can choose $k$ with $40^k/2^k>c$ ...)

-