0
$\begingroup$

The problem I have is asking me if $2^{2^{n + 1}} = O( 2^{2^n} )$?

This is my proof:

let constant $C = 16$, and $k = 1$ such that for all $n \geq k$
let $n = 1$

1: $2^{2^{1 + 1}} \leq C 2^{2^1}$
2: $2^{2^2} \leq 16 2^2$
3: $2^4 \leq 16 4$
4: $16 \leq 64$ is true. Q.E.D.

Did I properly prove that $2^{2^{n + 1}} == O( 2^{2^n} )$? Is there anything else I need to show for this proof to be complete?

  • 0
    Sorry David but what is $ 2^{2^n} $ showing me?2012-01-16

1 Answers 1

2

Your proof is incorrect; you showed that $2^{2^{n+1}}\le C\cdot 2^{2^n}$ for one value of $n$. If you want to show that $2^{2^{n+1}}=O( 2^{2^n})$, then you need to find a positive constant $C$ so that $\tag {1}2^{2^{n+1}}\le C \cdot2^{2^n}$ for all $n$ sufficiently large (note the same $C$ must work for all $n$ sufficiently large).

But as $\tag{2} 2^{2^{n+1}} =2^{2\cdot 2^n}=2^{2^n+2^n} = 2^{2^n}\cdot 2^{2^n}, $ this would be impossible to do.

Indeed, suppose $C>0$ and that $(1)$ holds for all $n>m$.

Then from $(2)$ $ 2^{2^n}\cdot 2^{2^n}\le C \cdot2^{2^n};$ whence $ 2^{2^n} \le C, $ for all $n>m$. But this can't happen since $\lim\limits_{n\rightarrow\infty} 2^{2^n}=\infty$.

  • 0
    @TheFuzz More or less. $C$ must be positive constant. But because of the above, there isn't one. I'll expand the answer.2012-01-16