Proof by InductionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/