SOLUTION: Prove by mathematical induction that: 2^2n - 1 is divisible by 3 for all positive integers n

Algebra ->  Sequences-and-series -> SOLUTION: Prove by mathematical induction that: 2^2n - 1 is divisible by 3 for all positive integers n      Log On


   

Question 909567: Prove by mathematical induction that:

2^2n - 1 is divisible by 3 for all positive integers n
Answer by Edwin McCravy(20056) About Me  (Show Source):
You can put this solution on YOUR website!
What we are to prove is that for any positive integer n,

2%5E%282n%29-1 is divisible by 3, that is, it is a multiple of 3.

For n=1

2%5E%282%281%29%29-1=2%5E2-1+=4-1=3. 3 is a multiple of 3.

So it's true for n=1 

We must prove that if you know it's true for integer n=k, 
then it will be true for n=k+1.

Assume it's true for n=k.

2%5E%282k%29-1=3m for some positive integer m

Multiply both sides by 2%5E2

2%5E2%2A2%5E%282k%29-2%5E2=2%5E2%2A3m for some positive integer m
2%5E2%2A2%5E%282k%29-4=4%2A3m for some positive integer m

2%5E%282k%2B2%29-4=12m

Write -4 as -1-3

2%5E%282%28k%2B1%29%29-1-3=12m

2%5E%282%28k%2B1%29%29-1=12m%2B3

2%5E%282%28k%2B1%29%29-1=3%284m%2B1%29%7D%7D%2C+thus+%7B%7B%7B2%5E%282%28k%2B1%29%29-1 is a
multiple of 3.

Therefore since the theorem is true for n=k=1, it's true for n=k+1=2.

And since the theorem is true for n=k=2, it's true for n=k+1=3

Thus since the theorem is true for n=k=3, it's true for n=k+1=4

And this goes on forever, for we've proved it can't stop!

Edwin