Proof by Induction

Date: 03/18/2003 at 05:01:37
From: TEA
Subject: Sum

Hello,

What is the expression for:

                          n
                         ----
                        \    
                        /     2 to the power of r
                         ----
                          r=0

How can we prove it?

Thanks,
Tony

Date: 03/18/2003 at 07:07:08
From: Doctor Jeremiah
Subject: Re: Sum

Hi Tony,

Write out the sum:

2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ...
 1  +  2  +  4  +  8  +  16 + ...

The sum of the first 2 terms equals  3 and the 3rd term is 4
The sum of the first 3 terms equals  7 and the 4th term is 8
The sum of the first 4 terms equals 15 and the 5th term is 16

See the pattern?  If you want to prove it I think induction
is the best way.

There is a good explanation of induction in the archives:

   Sum of n Odd Numbers
   http://mathforum.org/library/drmath/view/56866.html 

What we want to prove is that the sum of the first n terms is the n+1 
term's value minus one. Written mathematically we are trying to prove:

       n
     -----
      \
      /    2^r = 2^(n+1)-1
     -----
      r=0

Induction has three steps:
1) Prove it's true for one value.
2) Prove it's true for the next value.

The way we do step 2 is assume it's true for some arbitrary value (in 
this case k). We know it's true for one arbitrary value of k because 
of the base case. So if we can prove it's true for k+1, then we have 
proven it for all arbitrary values.

Step 1:  Base case n=0

       n
     -----
      \
      /    2^r = 2^0 = 1 = 2^1 - 1           TRUE
     -----
      r=0

Step 2:  Assume it's true for n=k

       k
     -----
      \
      /    2^r = 2^(k+1)-1                   ASSUMED
     -----
      r=0

Step 3:  Try to prove n=k+1

       k+1
     -----
      \
      /    2^r = 2^((k+1)+1)-1
     -----
      r=0

       k
     -----
      \
      /    2^r   + 2^(k+1) = 2^(k+2)-1
     -----
      r=0

     At this point we can substitute our assumption.
     If we prove this is true, that validates the assumption
     and all is fine.

     2^(k+1)-1 + 2^(k+1) = 2^(k+2)-1
     2*2^(k+1)-1 = 2^(k+2)-1
     2^((k+1)+1)-1 = 2^(k+2)-1
     2^(k+2)-1 = 2^(k+2)-1                   TRUE
     
     The assumption is true and the proof therefore is true.

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/