Induction Question

[Bripirate]

This isn't homework but I was playing around re-learning mathematical induction and I came across this problem. Prove that 2 + 2^2 + 2^3+ . . . +2^n = 2^(n+1). I understand that this works for n = 1 but not for the next four or so terms so I tried to fix it by setting it equal to 2^(n+1) - 2^n. This seems to work well for the first 4 terms but when I formulate the inductive hypothesis and try to prove it, I can't. Is this series incorrect and how do I go about finding the counter example? I get as far as 2^(k+1) -2^(k) + 2(k+1) = 2(k+2) -2^(k+1). Sorry about my lack of adeptness with LaTEX. Any advice would be appreciated.

[Flumble]

I believe that particular formula is supposed to be 2 + 2^1 + 2^2 + ... + 2^n = 2^(n+1).

[Bripirate]

Damn...too tired to even copy the problem down correctly. Thanks Flumble!!

[Bripirate]

I still don't see how to get the algebra to work out? I seem to get 2^(k+1) + 2^(k+1) = 2^(k+2). How are those equal? I don't know any laws for the addition/subtraction of exponents.

[Bripirate]

Wait...factor out a 2? Then 4K = 4K?

[Flumble]

I don't know any laws for the addition/subtraction of exponents.

Ah, that might be a problem for this problem. I have no idea how to properly explain the rule, but let's try anyway.
The product of two exponentiations (with the same base) is the same as summing the exponents: a^b * a^c = a^(b+c). Straightforward example (with an x because using only numbers feels like cheating): x*x = x^1 * x^1 = x^(1+1) = x^2.

So the reverse means you can turn those +1 and +2 in the exponents into seperate powers of two ...which you may or may not have already done judging by your vague 4K=4K response.

[elliptic]

To put it in more specific terms...

2^(k+1) = 2 * 2 * ... * 2 = the product of k+1 2s.

2^(k+1) + 2^(k+1) = 2 * 2^(k+1) = the product of... how many 2s?

Also...

Spoiler:

You can re-express the formula as 1 + 2^0 + 2^1 + ... + 2^n = 2^n+1.

So what you're proving is that, given a binary number comprising all "ones" (eg 1111), then adding 1 to that number will give a result with all trailing zeros, which is the next power of two (eg 1 + 1111 = 10000).

Which makes it more intuitive, hopefully

[Schrödinger's Wolves]

For n=0 the case is trivial: 2=2^(0+1)
Assuming the statement is true for n:
We have that 2+2^1+2^2+...+2^(n-1)+2^n=2^(n+1).
We also know that 2^(n+1)+2^(n+1)=2^(n+1)*2=2^(n+2).
Substituting 2+2^1+2^2+...+2^(n-1)+2^n for 2^(n+1) since they are equal:
We have 2+2^1+2^2+...+2^(n-1)+2^n+2^(n+1)=2^(n+2)=2^((n+1)+1) which is exactly the theorem for n+1.
So, since we have that the theorem is true for n=0, and we have that for all n, if it is true for n then it is true for n+1, we therefore know that the theorem is true for all natural numbers n.

[gmalivuk]

Since it's not clear whether the OP got it:

I still don't see how to get the algebra to work out? I seem to get 2^(k+1) + 2^(k+1) = 2^(k+2). How are those equal? I don't know any laws for the addition/subtraction of exponents.

2^(k+1)+2^(k+1)=2*2^(k+1)=2^(k+2)

a^b + a^b = 2*a^b, and for arbitrary values of a there's nothing more you could do. This problem works because a=2, and twice a power of 2 is the next power of 2, by definition.