Understanding Mathematical Induction: Solving 2^n Series Equation

[Stratosphere]

I was given the problem: For n \geq 1, 2 + 2^{2} + 2^{3} + 2^{4} + ... + 2^{n} = 2^{n+1} – 2.
I did the induction on it and got 2^{k+2}-2. I know this is the right answer but I don't know WHY. Could anyone explain it to me?

 

[rock.freak667]

Well for proving induction, you assume it is true for n=k. Then we prove true for n=k+1, meaning we show that the next term should be true as well...So basically you are saying that, for n=k your statement p(n) which is now p(k), is true implies that p(k+1) is true and by extension p(k) is proven true.

 

[Stratosphere]

How would you know if it's NOT true?

 

[qntty]

If the base case fails or if p(n) doesn't imply p(n+1)

 

[jgens]

Well, perhaps I'm misunderstanding your question but it seems like you're asking why mathematical induction works. The best treatment (by this I mean the simplest to understand) that I've seen used the well-ordering axiom so here goes nothing . . .

*Disclaimer* I'm not positive that this is the correct use of the well-ordering axiom or even the correct statement, this is just what one of my old textbooks says.

Well-Ordering Axiom: Every non-empty set of positive integers contains a least element. Essentially this means that if we consider a set of positive integers that is non-empty (contains some numbers), that set must have a smallest element or number. So, if we consider the non-empty set {2,3,4}, it contains a least element 2.

Proof by Induction: The proof begins by establishing that a given statement P(n) is true for n = 1. Now, let's assume that P(n) is not true for some values of n. Since this set of numbers is non-empty we can apply the well-ordering axiom. Therefore, there must be some least value n = k + 1 such that P(n) is not true. Since we know that P(n) is true when n = 1 and we know that P(n) is first false for n = k + 1, we can clearly see that P(n) must be true when n = k. Now, given that P(k) is true, if we can show that P(k + 1) is also true, that means that our assumption that P(n) was false for some positive integers n must have been incorrect. Therefore, P(n) is true for all positive integers n.

We can, of course modify this procedure slightly to fit the needs of the proof (suppose P(n) is only true if n > 3). What I liked a lot about this treatment is that it really explains why induction works and why we must use natural numbers.