# Thread: Proof by induction: 7^n + 2 is divisible by 3

1. ## Proof by induction: 7^n + 2 is divisible by 3

Use Proof by Mathematical induction to prove that 7^n + 2 is divisible by 3 for all n in the Natural Numbers.
First thing I guess is to label the equation;

$p(n) = 7^n + 2$

And then Show that it holds for n=1:

$p(1) = 7^1 + 2$
$p(1) = 9$

So it works for 1; 9 is divisible by 3.

Now for p(n+1)...

$p(n+1) = 7^{n+1} + 2$

$p(n+1) = 7 \cdot 7^{n} + 2$

Now how do I go about showing that that's divisible by 3?

2. ## Re: Proof by induction: 7^n + 2 is divisible by 3

we can do it my mathematical Induction: the steps as you pkow are
prove that the statement P(n) is true for n=1.
assume that P(k) is true.
finally establish that when P(k) is true it implies P(k+1) is true.
You have established that P(1) is true.
Now we assume P(k) is true that means 7^k + 2 = 3 m for some m in N. That gives 7^k = 3m -2------ [1]
For :P(k+1)
7^(k+1) + 2 = 7^k * 7 + 2 = 7 ( 3m - 2) + 2 Using (1)
= 21m -14 + 2
I am sure you can take it further

3. ## Re: Proof by induction: 7^n + 2 is divisible by 3

Or another way

$7 \cdot 7^n + 2 = (6 + 1)7^n + 2$

$\underbrace {6 \cdot 7^n}_{divisible \ by \ 3} + \underbrace{7^n + 2}_{divisible \ by \ 3}$

So the whole thing is divisible by 3.

4. ## Re: Proof by induction: 7^n + 2 is divisible by 3

Originally Posted by ibdutt
we can do it my mathematical Induction: the steps as you pkow are
prove that the statement P(n) is true for n=1.
assume that P(k) is true.
finally establish that when P(k) is true it implies P(k+1) is true.
You have established that P(1) is true.
Now we assume P(k) is true that means 7^k + 2 = 3 m for some m in N. That gives 7^k = 3m -2------ [1]
For :P(k+1)
7^(k+1) + 2 = 7^k * 7 + 2 = 7 ( 3m - 2) + 2 Using (1)
= 21m -14 + 2
I am sure you can take it further
Ah I get it, so you have to set the equation to 3m where m is a natural number.

And then at the end:
= 21m -14 + 2
= 21m - 12
= 3 (7m - 4)

Which is a multiple of 3 and so the solution will always be divisible by 3.

Originally Posted by agentmulder
$\underbrace {6 \cdot 7^n}_{divisible \ by \ 3} + \underbrace{7^n + 2}_{divisible \ by \ 3}$
How do you know that:

$\underbrace{7^n + 2}_{divisible \ by \ 3}$

That that's divisible by 3? I thought that's why I'm trying to prove, so I can't assume it's divisible by 3...

5. ## Re: Proof by induction: 7^n + 2 is divisible by 3

Originally Posted by Educated
Ah I get it, so you have to set the equation to 3m where m is a natural number.

And then at the end:
= 21m -14 + 2
= 21m - 12
= 3 (7m - 4)

Which is a multiple of 3 and so the solution will always be divisible by 3.

How do you know that:

$\underbrace{7^n + 2}_{divisible \ by \ 3}$

That that's divisible by 3? I thought that's why I'm trying to prove, so I can't assume it's divisible by 3...
That is the inductive step, you assume it holds for k = n and then you use that assumption to prove that it MUST hold when k = n + 1