Induction Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Bripirate
Posts: 29
Joined: Thu Oct 04, 2007 6:05 pm UTC
Contact:

Induction Question

Postby Bripirate » Mon Apr 03, 2017 10:14 pm UTC

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.

User avatar
Flumble
Yes Man
Posts: 1939
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Induction Question

Postby Flumble » Mon Apr 03, 2017 11:28 pm UTC

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

User avatar
Bripirate
Posts: 29
Joined: Thu Oct 04, 2007 6:05 pm UTC
Contact:

Re: Induction Question

Postby Bripirate » Mon Apr 03, 2017 11:43 pm UTC

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

User avatar
Bripirate
Posts: 29
Joined: Thu Oct 04, 2007 6:05 pm UTC
Contact:

Re: Induction Question

Postby Bripirate » Tue Apr 04, 2017 12:07 am UTC

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.

User avatar
Bripirate
Posts: 29
Joined: Thu Oct 04, 2007 6:05 pm UTC
Contact:

Re: Induction Question

Postby Bripirate » Tue Apr 04, 2017 12:10 am UTC

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

User avatar
Flumble
Yes Man
Posts: 1939
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Induction Question

Postby Flumble » Tue Apr 04, 2017 2:10 am UTC

Bripirate wrote: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.

User avatar
elliptic
Posts: 32
Joined: Tue Aug 14, 2012 2:21 pm UTC
Location: UK

Re: Induction Question

Postby elliptic » Tue Apr 04, 2017 11:19 am UTC

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
Posts: 14
Joined: Fri Mar 24, 2017 3:28 am UTC

Re: Induction Question

Postby Schrödinger's Wolves » Tue Apr 18, 2017 4:26 am UTC

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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Induction Question

Postby gmalivuk » Tue Apr 18, 2017 12:43 pm UTC

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

Bripirate wrote: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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 18 guests