Proof by induction?

Question

I am fine with the ordinary proofs i.e triangle nos but, dont know where to start on this one.

prove 8^n + 6 is divisable by 14

Answer 1

Prove a=8^n+6 is divisible by 14

We have 14=2*7, so both 2 and 7 must divide a

Step 1)
2 divides 8 <=> 2 divides 8^n
2 divides 6
From the above we have that 2 divides 8^2+6=a


Step 2)
If 7 divides 8^n+6 <=>
7 divides 8^n+6-7 <=>
7 divides 8^n-1
So if we show that 7 divides 8^n-1 then it is proven.

Lets suppose that for a specific number m:
7 divides 8^m-1 <=>
7 divides 8*(8^m-1) <=>
7 divides 8^(m+1)-8 <=>
7 divides 8^(m+1)-1
So if 7 divides 8^m-1 it also divides 8^(m+1)-1

Because we have:
a)7 divides 8^n-1 for n=1
b)given that for a specific number m 7 divides 8^m-1 it also divides 8^(m+1)-1
we conclude that
7 divides 8^n-1 for any number n>=1 <=>
7 divides 8^n+6=a for n>=1

From steps 1 (2 divides a), 2 (7 divides a) and fact that 2 and 7 are relatively primes (2 does not divide 7 nor does 7 divide 2) we conclude that 17 divides 8^n+6 for any n>=1.

Answer 2

We modify the expression as follows:

8^n + 6
(14 - 6)^n + 6
14k + (-6)^n + 6....where k is an integer
14k + 6((-6)^(n-1) + 1)

The polynomial ((-x)^m + 1) is divisible by (x+1), where m is any integer, so that we know that the expression (-6)^(n-1) +1) is divisible by (6+1) = 7, and that 6 is divisible by 2, so that 6((-6)^(n-1) + 1) is divisible by 14.

Therefore 8^n + 6 is divisible by 14

Addendum: Amit Y's induction proof is neat, but let's do his way a bit more clearly:

8^n + 6 = 14n
8^(n+1) + 6*8 = 14*8n
8^(n+1) + 6 + 42 = 14*8n
(8^(n+1) + 6) + 14*3 = 14*8n

Therefore 8^(n+1) + 6 is also divisible by 14, and the induction is completed.

Answer 3

Hi.

First, you VERIFY the conjecture.

For n = 1, 8^1 + 6 = 14
For n = 2, 8^2 + 6 = 70

Ok, so it works.

Next, we ASSUME that it works for all numbers such that n<=k.
This means that we are saying that it stops working for numbers larger than k.

Then, we SHOW that the conjecture holds true for n = k +1.

8^(k+1) + 6
8^(k+1) + 6 - [8^k + 6]

8^(k+1) - 8^k
8^k [8 - 1]

8^k * 7

Since divisibility by 14 is achieved by proving that a number is divisible both by 7 and 2 (if it's divisible by 8, as it is a power of 8, it must be divisible also by 2), we see that the difference is also divisible by 14.

Thus, we CONCLUDE that n applies also to k +1, and thus, proving that it applies to all counting numbers.

Hope this helps.

Answer 4

Check for n=1.

Then assume it is correct for any n and prove for n+1.
let m be a number such that 14m = 8^n + 6
8^(n+1) + 6 = 8 * 8^n + 6 = 8 * (8^n + 6 - 6) + 6 = 8 * (8^n +6) - 48 + 6 = 8*14m - 42.

8 * 14m is divisible by 14, and so is 42, and of course the difference between them.

QED

Answer 5

just guess and check or use a graphing calculator to find when it can be divided by 14.