# induction

• Nov 12th 2008, 09:01 PM
sabrina87
induction
show that

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

thank you (Nerd)
• Nov 12th 2008, 09:39 PM
mr fantastic
Quote:

Originally Posted by sabrina87
show that

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

thank you (Nerd)

I assume you're having trouble with step 3.

Then note:

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

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

$\displaystyle = 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 ........
• Nov 13th 2008, 08:51 AM
ThePerfectHacker
Quote:

Originally Posted by sabrina87
show that

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

thank you (Nerd)

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

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

Thus, $\displaystyle A_n \equiv 2^{n+2}+2^{n+1}+2^n = 2^n(1+2+2^2) \equiv 0 (\bmod 7)$.
• Dec 10th 2008, 06:44 PM
drthea
Quote:

Originally Posted by ThePerfectHacker
Here is a non-induction proof.
Let $\displaystyle A_n = 37^{n+2}+16^{n+1}+23^n$.

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

Thus, $\displaystyle 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?
• Dec 10th 2008, 07:45 PM
ThePerfectHacker
Quote:

Originally Posted by drthea
Hello,
could you explain the second solution, please?

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