Growth Rates of F(n) vs. F(n) + F(n-1) + ... F(1)

Question

I am trying to understand growth rates between a function and its sum recursively. For example I understand that if:

$F(n) = n$

Then the sum $n + (n - 1) + ... 2 + 1 = \frac{n(n-1)}{2}$ which is $O(n^2)$. Which means that $F(n) = O(sum)$.

However, I am having trouble understanding this concept for the function:

$F(n) = 2^n$

The answer is $F(n) = \Theta(sum)$ But I am not sure why it is $\Theta$ and not $O$.

Answer 1

You can show by induction (or using the geometric series formula), that $$2^1 + 2^2 + \ldots + 2^n = 2^{n+1} - 2$$ And you have that $2^{n+1} - 2 = 2(2^n - 1) = \Theta(2^n)$