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?

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

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.

:)

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...

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

:)