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

• May 24th 2013, 07:05 PM
Educated
Proof by induction: 7^n + 2 is divisible by 3
Quote:

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;

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

And then Show that it holds for n=1:

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

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

Now for p(n+1)...

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

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

Now how do I go about showing that that's divisible by 3?
• May 24th 2013, 08:28 PM
ibdutt
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
• May 25th 2013, 01:05 AM
agentmulder
Re: Proof by induction: 7^n + 2 is divisible by 3
Or another way

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

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

So the whole thing is divisible by 3.

:)
• May 25th 2013, 01:26 AM
Educated
Re: Proof by induction: 7^n + 2 is divisible by 3
Quote:

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.

Quote:

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

How do you know that:

$\displaystyle \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...
• May 25th 2013, 02:33 AM
agentmulder
Re: Proof by induction: 7^n + 2 is divisible by 3
Quote:

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:

$\displaystyle \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

:)