0

I need to prove that $2^{n+1} = \Theta(2^n)$?

To do this, I need to show that there are positive constants $c_1,c_2$ such that

$$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ ...for all sufficiently large $n$.

To find $c_2$, I know that I just need to find $O(2^n)$ which I have done below:

$$ \frac{f(n)}{g(n)} = \frac{2^{n+1}}{2^n}=\frac{2 \cdot {2^n}}{2^n} = 2 $$

Therefore, $c_2 = 2$.

Can anybody tell me how to find $c_1$?

Ben Grossmann
  • 225,327
User
  • 907

1 Answers1

2

There are several choices available, but here's a hint: What number, when multiplied to $2^n$, will give you $2^{n+1}$?

Ken
  • 3,751
  • That would be 2, right? Though I already found 2 as my $C_2$. – User Jun 05 '15 at 05:20
  • 1
    Yes indeed it would. It's okay, though: $c_1$ and $c_2$ can be the same. – Ken Jun 05 '15 at 05:21
  • I guess I am a bit confused. Can you provide reasoning to the logic here? Why did you want to take a number multiplied by $2^n$ to get $2^{n+1}$? – User Jun 05 '15 at 05:25
  • Well, to find a $c_1$ such that $c_1 2^n \leq 2^{n+1}$, it certainly suffices if we find a $c_1$ such that $c_1 2^n = 2^{n+1}$. It may not make sense to try this all the time, but sometimes it works. – Ken Jun 05 '15 at 05:27
  • @Ken I am afraid there is no other option here than to address the basic mistake in the question, more explicitely than what you are doing now. – Did Jun 05 '15 at 05:29
  • Ah OK gotcha, that makes sense! In the original answer, you said that there are several choices available. Can you explain how I could find another answer if I wanted? – User Jun 05 '15 at 05:32
  • Sure. Once you've found $c_1 = 2$ as something that achieves equality, other choices of $c_1$ which are less than $2$ (but still positive) would give you something less than $2 \cdot 2^n = f(n)$. – Ken Jun 05 '15 at 05:37
  • @Did I see what you're talking about, but Omnomnomnom seems to have addressed it. For my part, I was just happy to get back to asymptotic basics. ^_^ – Ken Jun 05 '15 at 05:45
  • 1
    @Ken Sorry to insist but comments are transient, only answers are meant to stay, hence you definitely should address the question in your answer. – Did Jun 05 '15 at 06:37