How to prove $n^6$ is big-O but not big-Omega of the function $(1.001)^n$

Question

I know that, $n^c \in \mathcal{O}(2^n)$ for any constant $c$. However, I don't know how to prove, or whether it is correct that, $n^c \in \mathcal{O}(1.001)^n$ for any constant $c$. Does anyone has an idea?

What I have tried so far:

By definition, $n^6 \in \mathcal{O}(1.001)^n \iff n^6 \leq c \cdot 1.001^n$ for $n \geq n_0$, where $n_0$ is a non-negative integer and $c$ is a positive integer.

How do I go from here?

Answer 1

The proofs for $n^c \in \mathcal O(2^n)$ and $n^c \in \mathcal O((1.001)^n)$ are basically the same. You can prove:

Proposition. For arbitrary constants $c > 0$ and $r > 1$, we have $n^c \in \mathcal O(r^n)$.

Proof. First, note that $$\begin{align*} n^c \le Cr^n &\iff \log n^c \le \log Cr^n\\ &\iff c\log n - n\log r \le \log C. \end{align*}$$ Thus it suffices to prove that a function $$ f(x) = c\log x - x\log r \quad (x > 0)$$ is bounded from above. As $$f'(x) = \frac{c}{x} - \log r \begin{cases} > 0 \quad \left(x < \tfrac{c}{\log r}\right)\\ = 0 \quad \left(x = \tfrac{c}{\log r}\right)\\ < 0 \quad \left(x > \tfrac{c}{\log r}\right), \end{cases}$$ the function $f$ has a maximum $f\left(\tfrac{c}{\log r}\right) = c\log \tfrac{c}{\log r} - c = \log \left(\tfrac{c}{e\log r}\right)^c$.

Hence we get $n^c \le \left(\tfrac{c}{e\log r}\right)^cr^n$ for $n \ge 1$; in particular, $n^c \in \mathcal O(r^n)$.

Answer 2

For any positive $n$:

\begin{align*} 1.001^n&=e^{n \ln 1.001}\\ &=\sum_{k=0}^\infty \frac{(n\ln 1.001)^k}{k!}\\ &>\frac{(n \ln 1.001)^7}{7!}&\text{(because all the terms in the sum are positive)}\\ &=\frac{(\ln 1.001)^7}{7!}n^7 \, . \end{align*}