document.write( "Question 1096592: Use mathematical induction to prove 3 is a factor of 4^n - 1. I'm realky confused. Please help me. Thank you so much. \n" ); document.write( "

Algebra.Com's Answer #711021 by greenestamps(13200) $\"\"$ $\"About$

You can put this solution on YOUR website!

I find proofs using mathematical induction very pleasing. You show that a proposition is true for some starting value; then you show that if it is true for an arbitrary value it logically follows that it is also true for the next value; and then you logically conclude that it is always true.

\n" ); document.write( "So let's look at the proposition we are trying to prove:

\n" ); document.write( " $\"4%5En-1\"$ is divisible by 3

\n" ); document.write( "We first need to show it is true for some initial value. Usually that initial value is 1; but sometimes it is 0, or in some cases it might be some small positive integer like 3 or 4. In this example, starting with n=0 is not very interesting, because the statement then says that 0 is divisible by 3. So let's start with n=1; then the statement says

\n" ); document.write( " $\"4%5E1-1+=+4-1+=+3\"$ is divisible by 3.

\n" ); document.write( "That's certainly true, so we are done with the first step.

\n" ); document.write( "To finish the proof, we need to show that assuming the statement is true for some integer k, it logically follows that it is also true for the integer k+1.

\n" ); document.write( "So we assume this is true:

\n" ); document.write( " $\"4%5Ek-1\"$ is divisible by 3.

\n" ); document.write( "We need to show that, with this assumption, we can show that $\"4%5E%28k%2B1%29-1\"$ is also divisible by 3. So let's look at that expression $\"4%5E%28k%2B1%29-1\"$

\n" ); document.write( " $\"4%5E%28k%2B1%29-1+=+4%5Ek%2A4%5E1-1+=+4%284%5Ek%29-1\"$

\n" ); document.write( "At this point, we have an expression $\"4%5Ek\"$ in our work. We know (we assumed!) that $\"4%5Ek-1\"$ is divisible by 3; so we want to somehow get that expression $\"4%5Ek-1\"$ in our work. So we continue with...

\n" ); document.write( " $\"4%284%5Ek%29-1+=+4%284%5Ek-1%29-1%2B4\"$

\n" ); document.write( "In that step we first subtracted 4 (by adding the -1 in the parentheses) and then added 4 to balance things out. Then continuing further...

\n" ); document.write( " $\"4%284%5Ek-1%29-1%2B4+=+4%284%5Ek-1%29%2B3\"$

\n" ); document.write( "But we know $\"4%5E%28k-1%29\"$ is divisible by 3, so $\"4%284%5Ek-1%29\"$ is divisible by 3; and clearly 3 is divisible by 3.

\n" ); document.write( "So we have shown that $\"4%5E%28k%2B1%29-1\"$ is divisible by 3 if $\"4%5Ek-1\"$ is divisible by 3 -- and thus we have completed the proof by mathematical induction. \n" ); document.write( "

\n" );