Hello,

I know this is a pretty basic question for you guys but I'm trying to learn induction and I need to see how this done please help with this problem...

2^{0} + 2^{1} + 2^{2} +... + 2^{n} = 2^{n+1} -1 is true whenever n is a positive integer.

Thanks for your help Kyle

Kyle,

Let p(n) be the statement that 2^{0} + 2^{1} + 2^{2} +... + 2^{n} = 2^{n+1} -1.
You need to first check this out for n = 1, i.e. 2^{0} + 2^{1} = 3 = 2^{1+1} -1. Next assume that you have checked it out for n = 1, ..., k for some k > = 1. In particular you now know that 2^{0} + 2^{1} + 2^{2} + ...+ 2^{k} = 2^{k+ 1} -1, i.e. p(k) holds - this is the induction hypothesis . What is necessary to complete the proof is to show that this knowledge implies p(k+1) holds.

Now 2^{0} + 2^{1} + 2^{2} + ...+ 2^{k+1} = 2^{0} + 2^{1} + 2^{2} + ...+ 2^{k} + 2^{k+1} = 2^{k+1} -1 + 2^{k+1} (using the induction hypothesis) = 2x2^{k+1} -1 = 2^{k+2} -1 as required. Thus p(k) holds implies that p(k+1) holds and since p(1) is true, p(n) is true for all n >= 1.

Penny