![\"\"](\"/images/stars/stars-13.gif\")
You can put this solution on YOUR website!
To prove a formula using mathematical induction, you need to
\n" ); document.write( "(1) prove it is true for some \"beginning\" value (usually 0 or 1); and
\n" ); document.write( "(2) show that if it is true for some value k then it follows that it is also true for k+1.
\n" ); document.write( "Having shown that the formula is true for some beginning value, and having shown that its being true for any number implies that it is also true for the next number, we can conclude that it is true for any number.
\n" ); document.write( "The formula you are trying to prove is
\n" ); document.write( "2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1)-1
\n" ); document.write( "Step (1): Show the formula is true for n=1. For n=1, the formula says
\n" ); document.write( "2^0 + 2^1 = 2^2-1
\n" ); document.write( "1+2 = 4-1
\n" ); document.write( "3 = 3
\n" ); document.write( "The formula is true for n=1; we have finished step (1).
\n" ); document.write( "Step (2): assume the formula is true for some value k, then show that it follows that it is also true for k+1.
\n" ); document.write( "For n=k, the formula says
\n" ); document.write( "2^0 + 2^1 + 2^2 + ... + 2^(k-1) + 2^k = 2^(k+1)-1
\n" ); document.write( "We assume that is a true statement, and we show that it follows that the formula is also true for (k+1). For (k+1), the formula says
\n" ); document.write( "2^0 + 2^1 + 2^2 + ... + 2^(k-1) + 2^k + 2^(k+1) = 2^(k+2)-1
\n" ); document.write( "What we need to show is that we get exactly that expression when we add the next power of 2.
\n" ); document.write( "We know the sum of all terms but the last on the left is equal to 2^(k+1)-1 (it is what we assumed....). So now let's add the last term to this expression and simplify:
\n" ); document.write( "(2^(k+1)-1) + 2^(k+1) = 2^(k+1) + 2^(k+1) - 1 = 2(2^(k+1))-1 = 2^(k+2)-1
\n" ); document.write( "And that is exactly what we wanted to show.
\n" ); document.write( "We have completed both of the required steps to show by mathematical induction that the formula is true for all values of n.\r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "