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⁰ + 2¹ + 2² +... + 2ⁿ = 2ⁿ⁺¹ -1 is true whenever n is a positive integer.

Thanks for your help Kyle

Kyle,

Let p(n) be the statement that 2⁰ + 2¹ + 2² +... + 2ⁿ = 2ⁿ⁺¹ -1. You need to first check this out for n = 1, i.e. 2⁰ + 2¹ = 3 = 2¹⁺¹ -1. Next assume that you have checked it out for n = 1, ..., k for some k > = 1. In particular you now know that 2⁰ + 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⁰ + 2¹ + 2² + ...+ 2^k+1 = 2⁰ + 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