Induction Question
Moderators: gmalivuk, Moderators General, Prelates
Induction Question
This isn't homework but I was playing around relearning 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.
Re: Induction Question
I believe that particular formula is supposed to be 2 + 2^1 + 2^2 + ... + 2^n = 2^(n+1).
Re: Induction Question
Damn...too tired to even copy the problem down correctly. Thanks Flumble!!
Re: Induction Question
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.
Re: Induction Question
Wait...factor out a 2? Then 4K = 4K?
Re: Induction Question
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.
Re: Induction Question
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...
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:

 Posts: 14
 Joined: Fri Mar 24, 2017 3:28 am UTC
Re: Induction Question
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^(n1)+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^(n1)+2^n for 2^(n+1) since they are equal:
We have 2+2^1+2^2+...+2^(n1)+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.
Assuming the statement is true for n:
We have that 2+2^1+2^2+...+2^(n1)+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^(n1)+2^n for 2^(n+1) since they are equal:
We have 2+2^1+2^2+...+2^(n1)+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
 GNU Terry Pratchett
 Posts: 26605
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Induction Question
Since it's not clear whether the OP got it:
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.
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.
Who is online
Users browsing this forum: Thesh and 10 guests