Question 9.2: Prove that TIME(2^n) ⊊ ( TIME(2^2n).

The containment TIME (2^{n}) ⊆ TIME (2^{2n+}) holds because 2^{n} \leq 2^{2n}. The containment is proper by virtue of the time hierarchy theorem. The function 2^{2n} is time constructible because a TM can write the number 1 followed by 2n 0s in O (2^{2n}) time. Hence the theorem guarantees that a language A exists that can be decided in O (2^{2n}) time but not in o (2^{2n}/ \log 2^{2n}) = o (2^{2n}/ 2n) time. Therefore, A \in TIME (2^{2n}) but A \notin TIME (2^{n}).