3^2n-1 is divisible by 8 for every positive integer n. Using Induction?

Question

Does someone know how to do this, i dont understand induction at all. To me its very complicated i cant get it, can someone help me.

Answer 1

Induction means you have to prove two things:

1. "If it's true for one number, it's true for the next number"

and:

2. "It's true for the number 1" (or 0, or whatever your "starting" number is)

In our case, the "starting" number is the first positive integer, 1.  So let's do the easy part first and show it's true for n=1:

3^[2·1] - 1

= 3² - 1

= 8

This is definitely divisible by 8.  Check.

Now we have to prove, ""If it's true for one number, it's true for the next number".

In our case that means we have to prove:

"If we can find some number "k" such that 3^(2k) - 1 is divisible by 8, then it's a fact that 3^(2[k+1]) - 1 is also divisible by 8."

So let's pretend we found such a "k", and see if we can demonstrate that 3^(2[k+1]) - 1 is (also) divisible by 8.

Note that:

3^(2[k+1]) - 1 = 3^(2k+2]) - 1

= (3^(2k))(3²) - 1

= (3^(2k))(8+1) - 1

= (3^(2k))(8) + 3^(2k) - 1

Well, we know that (3^(2k))(8) is divisible by 8 because, hey, it's got that "8" hanging on it.

And we know that 3^(2k) - 1 is divisible by 8, because we postulated that at the beginning of the proof.

So we have:

(something divisible by 8) + (something else divisible by 8)

And such a sum must be divisible by 8.  QED.

So we've proved that, "if it works for one number, it works for the next number."

So that means, if it works for 1 (which it does, we already tested that), then it works for 2.  So we've proved that it works for 2.

And if it works for 2, then it must work for 3.

And if it works for 3, then it must work for 4.

And so on forever.  So in the end, it works for all the positive integers.  And that's induction.