Proof by Induction that 3^(4n)-1 is divisible 8.

[Miss_Hickey]

I am trying to use induction to prove that 3^(4n)-1 is divisible 8.

Here is my progress so far:

Step One: Prove true for n=1

3^(4x1)-1=80​

80 is divisible by 8.​

Step Two: Assume true for n=k

Let M be any integer. Thus, 8M is divisible by 8.
3^(4n-1)=8M
3^(4k-1)=8M​

Step Three: Prove true for n=k+1

3^[4(k+1)]-1
= 3^(4k+4)-1​

Any assistance with my next step would be hugely appreciated.

 

[Dr.Peterson]

Step One: Prove true for n=1

3^(4x1)-1=80​

80 is divisible by 8.​

Step Two: Assume true for n=k

Let M be any integer. Thus, 8M is divisible by 8.
3^(4n-1)=8M
3^(4k-1)=8M
​

Step Three: Prove true for n=k+1

3^[4(k+1)]-1
= 3^(4k+4)-1​

Thanks for showing your work!

Your second step should be stated a little differently, as it is not true for ANY integer M; and you also moved an important parenthesis. I would say this:

Step Two: Assume true for n=k
​

Then there exists some integer M such that 3^(4k)-1=8M
​

What you need to do in step 3 is to try to write 3^(4k+4)-1 in a form to which you can apply the fact that 3^(4k)-1=8M. I would start by expanding it to 3^(4k)*3^4-1. Then think about factoring this, hoping that one factor will turn out to be a multiple of 8.

 

[JeffM]

I quite dislike the way that proofs by induction are usually taught and presented.

\(\displaystyle \text {PROVE that: } m \in \mathbb N \implies \exists \ m_n \in \mathbb N+ \text { such that } 3^{4n} - 1 = 8m_n.\)

\(\displaystyle n = 1 \implies 3^{4n} - 1 = 81 - 1 = 8 * 10 \implies m_1 = 10 \text { and } 10 \in \mathbb N^+.\)

This was step 1.

Moreover step 1 PROVED that there is AT LEAST one number for which the proposition is true, and there may possibly be more than one. So there is no need to assume anything in step 2. It is a traditional but sloppy usage that confuses students. Step 2 deals with an arbitrary one of the numbers for which the proposition is now KNOWN to be true.

\(\displaystyle \exists \ k \text { and } m_k \in \mathbb N^+ \text { such that } 3^{4k} - 1 = 8m_k.\)

Now you deal with k + 1.

\(\displaystyle 8^{4(k+1)} = 8 * 8 ^{4K} = 8 * 8m_k.\)

Now what?