# Proof by Induction - Divisibility Proofs

• Sep 25th 2011, 02:43 PM
GrigOrig99
Proof by Induction - Divisibility Proofs
Prove by induction that 13^n - 6^(n - 2) is divisible by 7, n subset N.

Step 1: n = 1...

13^1 - 6^(1 - 2) = 13 - 6^-1 = 13 - 0.1666 = 12.833

Can someone help me spot where I've gone wrong on the calcualtion to prove n = 1 yields a number divisible by 7?

Thank you.
• Sep 25th 2011, 03:19 PM
Re: Proof by Induction - Divisibility Proofs
Quote:

Originally Posted by GrigOrig99
Prove by induction that 13^n - 6^(n - 2) is divisible by 7, n subset N.

Step 1: n = 1...

13^1 - 6^(1 - 2) = 13 - 6^-1 = 13 - 0.1666 = 12.833

Can someone help me spot where I've gone wrong on the calcualtion to prove n = 1 yields a number divisible by 7?

Thank you.

I think you need to start from n=2.
• Sep 25th 2011, 03:55 PM
GrigOrig99
Re: Proof by Induction - Divisibility Proofs
Thanks. I suppose it seems obvious, but all the examples in the book were operating from n = 1, so I figured I didn't have the choice.
• Sep 25th 2011, 04:34 PM
Re: Proof by Induction - Divisibility Proofs
Suppose $13^k-6^{k-2}$ is divisible by 7

Is $13^{k+1}-6^{k-1}$ also divisible by 7 ?

$(13)13^k-(6)6^{k-2}=(14)13^k-(7)6^{k-2}-\left[13^k-6^{k-2}\right]$

so the inductive proof is verified.
You just need to know which value of n it becomes valid for.
• Sep 25th 2011, 05:39 PM
GrigOrig99
Re: Proof by Induction - Divisibility Proofs
Got it. Thanks.
• Sep 26th 2011, 03:51 AM
Re: Proof by Induction - Divisibility Proofs
Proof By Induction tries to show the following...

Proposition being true for n=a causes the proposition to be true for n=a+1,
being true for n=a+1 in turn causes it to be true for n=a+2,
being true for n=a+2 in turn causes it to be true for n=a+3,
which in turn causes it to be true for n=a+4,
which in turn causes it to be true for n=a+5,
which in turn...... all the way to infinity.

We show this for every pair of terms in general using n=k and n=k+1.

It's like Japanese dominoes.

The value "a" is most often 1, but may be otherwise.