Why Does 2^n+1 Equal 2 * 2^n?

algoPhobic

New member
Joined
Jan 17, 2017
Messages
15
Hello,

I'm a computer science enthusiast. I'm trying to teach myself Algorithm Analysis. I'm not in a formal classroom type situation. So, I do not have the luxury of getting clarification or guidance from a teacher. All I have to go on is my computer science books, and faded memories of my grade school and high school algebra.

In Skiena's, The Algorithm Design Manual, there is a "key observation" {2n+1 = 2· 2n} in the following problem statement that I'm failing to understand...

Code:
[I]Is 2[SUP]n+1[/SUP] = O(2[SUP]n[/SUP])? Well, f(n) = O(g(n)) iff (if and only if) there exists a 
constant c such that for all sufficiently large n f(n) ≤ c · g(n). Is there? The 
key observation is that [B]2[SUP]n+1[/SUP] = 2· 2[SUP]n[/SUP][/B], so 2 · 2n ≤ c · 2[SUP]n[/SUP] for any c ≥ 2.[/I]

I understand the majority of what is being explained there. It's only the 2n+1 = 2· 2n that has me stumped. Please, can anybody talk me through an explanation of why 2n+1 = 2· 2n

I would be grateful if anybody could please advise me on what particular Algebra concepts I should bone up on that would give me a quick high level understanding of 2n+1 = 2· 2n.

Thank you in advance for your help.
 
Code:
Is 2n+1 = O(2n)? Well, f(n) = O(g(n)) iff (if and only if) there exists a 
constant c such that for all sufficiently large n f(n) ≤ c · g(n). Is there? The 
key observation is that 2n+1 = 2· 2n, so 2 · 2n ≤ c · 2n for any c ≥ 2.

I understand the majority of what is being explained there. It's only the 2n+1 = 2· 2n that has me stumped. Please, can anybody talk me through an explanation of why 2n+1 = 2· 2n
It is simply a law of exponents: \(\displaystyle \large 2^{a+b}=(2^a)\cdot(2^b)\)

Therefore: \(\displaystyle 2^{n+1}=2^n\cdot 2^1=2\cdot 2^n\).
 
It is simply a law of exponents: \(\displaystyle \large 2^{a+b}=(2^a)\cdot(2^b)\)

Therefore: \(\displaystyle 2^{n+1}=2^n\cdot 2^1=2\cdot 2^n\).

Eureka!

You're AWESOME, pka! Thanks a 106 ;د)
 
Another way you might approach it is to think about what raising something to a power really means, and by doing so you'll actually derive that formula instead of it being some magical, mystical thing you memorize and it works but you'll be darned if you know how or why. Returning to the basics, a power is essentially just repeated multiplication. 2n represents \(\displaystyle 2 \cdot 2 \cdot ... \cdot 2\), with n copies of 2, and 2n+1 then represents: \(\displaystyle 2 \cdot 2 \cdot 2 \cdot ... \cdot 2\), but with n+1 copies of 2.

From this, we can see that if we start with 2n+1 and "take away" one copy of two, we're left with the full expression we earlier noted was equal to 2n. Then, to ensure equality, we have to "restore" that "missing" copy of 2. When I was first learning this concept, what I just said seemed very abstract and I struggled with it. I found it helpful to consider actual concrete numbers to see what was happening. If we consider the case of n=4:

\(\displaystyle 2^4=2 \cdot 2 \cdot 2 \cdot 2=2 \cdot (2 \cdot 2 \cdot 2)=2 \cdot 2^3\)
 
Top