induction

**sabrina87** · November 12th 2008, 09:01 PM

show that

37^n+2 + 16^n+1 + 23^n is divisible by 7 whenever n is natural

thank you

**mr fantastic** · November 12th 2008, 09:39 PM

Originally Posted by sabrina87

show that

37^n+2 + 16^n+1 + 23^n is divisible by 7 whenever n is natural

thank you

I assume you're having trouble with step 3.

Then note:

$37^{k+3} + 16^{k+2} + 23^{k+1} = 37 \cdot 37^{k+2} + 16 \cdot 16^{k+1} + 23 \cdot 23^{k}$

$= 37 \left( 37^{k+2} + 16^{k+1} + 23^{k} \right) - 21 \cdot 16^{k+1} - 14 \cdot 23^k$

$= 37 \left( 37^{k+2} + 16^{k+1} + 23^{k} \right) - 7 \left(3 \cdot 16^{k+1} + 2 \cdot 23^k\right)$

which is divisible by 7 due to step 2 ........

**ThePerfectHacker** · November 13th 2008, 08:51 AM

Originally Posted by sabrina87

show that

37^n+2 + 16^n+1 + 23^n is divisible by 7 whenever n is natural

thank you

Here is a non-induction proof.
Let $A_n = 37^{n+2}+16^{n+1}+23^n$ .

Note $37^{n+2}\equiv 2^{n+2} (\bmod 7)$ , $16^{n+1}\equiv 2^{n+1}(\bmod 7)$ , $23^n\equiv 2^n(\bmod 7)$ .

Thus, $A_n \equiv 2^{n+2}+2^{n+1}+2^n = 2^n(1+2+2^2) \equiv 0 (\bmod 7)$ .

**drthea** · December 10th 2008, 06:44 PM

Originally Posted by ThePerfectHacker

Here is a non-induction proof.
Let $A_n = 37^{n+2}+16^{n+1}+23^n$ .

Note $37^{n+2}\equiv 2^{n+2} (\bmod 7)$ , $16^{n+1}\equiv 2^{n+1}(\bmod 7)$ , $23^n\equiv 2^n(\bmod 7)$ .

Thus, $A_n \equiv 2^{n+2}+2^{n+1}+2^n = 2^n(1+2+2^2) \equiv 0 (\bmod 7)$ .

Hello,
could you explain the second solution, please?

**ThePerfectHacker** · December 10th 2008, 07:45 PM

Originally Posted by drthea

Hello,
could you explain the second solution, please?

The result you need to know here is that if $a\equiv b(\bmod c) \implies a^k \equiv b^k (\bmod c)$ .

Thread: induction

LinkBack

Thread Tools

Display

induction

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Rigorously prove the principle of complete induction from mathematical induction??

induction help

Mathemtical Induction Proof (Stuck on induction)

Induction!

Search Tags