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

[enian]

Homework Statement

Prove by induction that,
3^(2n) - 1 is an integral multiple of 8
for all positive n >= 1.

Homework Equations

3^(2n) - 1

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.

 

[neutrino]

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

 

[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...

 

[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

 

[neutrino]

Go back to the usual notation...

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

 

[Ks. Jan Jenkins]

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

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.

 

[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 ?

 

[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?

 

[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}

 

[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

 

[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.

 

[enian]

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

 

[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.)

 

[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) = ?

 

[neutrino]

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

Yes, 9 times 3 raised to 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) = ?

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

 

[D H]

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?

 

[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?

 

[D H]

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.