# Induction: 3^(2n) - 1 is an integral multiple of 8

1. Sep 2, 2007

### enian

1. The problem statement, all variables and given/known data
Prove by induction that,
3^(2n) - 1 is an integral multiple of 8
for all positive n >= 1.

2. Relevant equations
3^(2n) - 1

3. The attempt at a solution

First I plugged in some values for n..

Some values I plugged in
(1) 3^2(1) - 1 = 8
(2) 3^2(2) - 1 = 80
(3) 3^2(3) - 1 = 728
(4) 3^2(4) - 1 = 6560
(5) 3^2(5) - 1 = 59048

These answers are all divisible by 8.
3^(2n) - 1 = 8x ?? Would that be correct?
3^(2n+1) - 1 = ???? How do I show this next step?
I don't have an example of a multiple variable induction problem so I am not really sure how it's supposed to work.

2. Sep 2, 2007

### neutrino

I don't see multiple variables. Use the normal method of solving a problem by induction.

3. Sep 2, 2007

### Ks. Jan Jenkins

To prove something by induction, for some statement P(n) where n is some positive integer, you must simply do the following:

1/ Show that it is true for k=1, that is P(k) is true.

2/ Show that for each k>=1 that P(k+1) is true.

For the first part, you have already done this:

3^2*1 -1 = 8 -> it is divisible by 8.

Now just do the second part !

HINT : You can change this notation to 3^2n = 1 mod 8 to make life a little easier....

4. Sep 2, 2007

### enian

Hmm, mod 8? We never covered that in class so I wasn't sure of the notation.

So I have 3^2n = 1 mod 8 as my P(n) statement and now I need to show that the statement is also true for 3^2(n+1) = 1 mod 8.
So I multiply both side by two three's (or 9) to get the + 1 portion of the exponent...

3*3[3^2(n)] = 3*3[1 mod 8]
Which expands out to..
3^2n+2 = 3*3[1 mod 8]
3^2(n+1) = 3*3[1 mod 8]

I don't think my teacher would enjoy the mod notation. lol

5. Sep 2, 2007

### neutrino

Go back to the usual notation...

Start with $$3^{2(n+1)} - 1$$

6. Sep 2, 2007

### Ks. Jan Jenkins

oof....

3^2n = 1 mod 8 means that the remainder of 3^2n when divided by 8 is 1. It is another way of saying that 3^2n - 1 is a multiple of 8 (3^2n - 1 = 0 mod 8).

3^2(n+1) = 3^(2n+2) = (3^2n)*(3^2) = (3^2n)*(9) = (3^2n)*1 mod 8

But since you haven't done modulus arithmetic, you probably won't understand how to use this - the main argument being that 3^2n and 3^2(n+1) have the same remainder mod 8.

Just do step 2 using the notation that you are familiar with, as neutrino has said.

7. Sep 2, 2007

### dextercioby

Forget the mod. Think induction. P(n)---->P(n+1). If 8/9^n -1 , then 9^n -1 =8k for some k in N. Then you need to show that 8/9^(n+1) -1 . Which means that 8/9 * 9^n -1 or 8/(8+1)* 9^n -1 . Can you take it from here ?

8. Sep 2, 2007

### enian

Okay so..

$$3^{2n}-1 = something*8$$
$$3^{2n}-1 = 8(k)$$
$$\frac{3^{2n}-1}{8} = k$$

We want to show that
$$\frac{3^{2(n+1)+1}-1}{8} = multiple.of.8$$

$$9(\frac{3^{2n}-1}{8}) = 9(k)$$
$$\frac{3^{(2n+2)}-9}{8} = 9k$$
$$\frac{(3^{2n})(3^{2})-9}{8} = 9k$$
$$\frac{(3^{2n})(9)-9}{8} = 9k$$

Am I headed in the right direction?

Last edited: Sep 2, 2007
9. Sep 2, 2007

### rock.freak667

Yep, you are about 2 or 3 lines away from showing that is always a multiple of 8

HINT:$$3^{2n}-1=8k$$
try finding an expression for $$3^{2n}$$

10. Sep 2, 2007

### enian

$$\frac{(3^{2n})(9)-9}{8} = 9k$$

so from this..

$$8(\frac{(3^{2n})(9)-9}{8}) = 8(9k)$$
$$3^{2n}(9)-9} = 72k$$
$$3^{2n}(9)} = 72k+9$$
$$3^{2n}(9) = 9(8k+1)$$
$$3^{2n}(9) = 3^{2n}(9)$$
$$1 = 1???$$

I'm lost. lol

11. Sep 2, 2007

### matt grime

Where did that first line come from?

We know, by assumption that 3^2n -1 is an integer multiple of 8, now, we need to take 3^2(n+1) -1 and some how write it in terms of 3^2n-1 and some other terms, so do it - this is the only thing in induction as I've told you before - relate the n+1st statement to the n'th statement.

12. Sep 3, 2007

### enian

Well, that's what I was trying to do. I don't see how your advice helps.

13. Sep 3, 2007

### neutrino

$$3^{2(n+1)} - 1= 9.3^{2n} - 1 = ...$$

Is there a way you can factor out that 9?

(It is assumed that $3^{2n} - 1$ is a multiple of eight.)

14. Sep 3, 2007

### enian

Where did the 9.3 come from? or was it supposed to be $$9(3^{2n})$$

The only ways I see to factor that is either by factoring it leaving you with
$$9(3^{2n} - 1/9)$$

or, by adding the - 1 to the other side.. ?

I think you're suggesting I substitute the $$3^{2n} - 1$$ for some expression that is a multiple of 8, but I have no idea what that would be.

9(8k) = ?

15. Sep 3, 2007

### neutrino

Yes, 9 times 3 raised to 2n.

Or you could rewrite the 1 and 9 - 8. [or the -1 as (-9 + 8), if you prefer.]

16. Sep 3, 2007

### D H

Staff Emeritus
Neutrino simply factored a 9 out of $$3^{2(n+1)}$$, like this: $$3^{2(n+1)} = 3^{2n+2} 3^2\cdot3^{2n}= 9\cdot3^{2n}$$. You simply have to show that if $$3^{2n}-1= k_n\cdot8$$ then $$3^{2(n+1)}-1=k_{n+1}\cdot8$$. Using the expansion, this becomes $$9\cdot3^{2n}-1=k_{n+1}\cdot8$$. Can you proceed from here?

17. Sep 4, 2007

### enian

Yea I see what you mean. This may be a dumb question but how is $$k_{n}$$ ever going to become $$k_{n+1}$$ since we don't know what k is?

18. Sep 4, 2007

### D H

Staff Emeritus
Ok. Time for an even bigger hint. Induction always starts by assuming the induction relation is true for some value of $n$, in this case, that

$$3^{2n}-1 = k_n\cdot 8$$

which is obviously true for $n=1$ with $k_1=1$.
Next step: Expand the relationship for $n+1$:

$$3^{2(n+1)}-1 = k_{n+1}\cdot 8$$

expanding the exponential term, this becomes

$$9\cdot3^{2n}-1 = k_{n+1}\cdot 8$$

You already know that $3^{2n}-1 = k_n\cdot 8$ or $3^{2n} = 1+k_n\cdot 8$ Insert this in the above expansion.