Proof by induction: 7^n + 2 is 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

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

How do you know that:

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:

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

:)