# Induction Proof

• February 26th 2009, 05:26 PM
DiscreteW
Induction Proof
Prove that for all $n \geq 1$, prove $5$ divides $8^n - 3^n$ using inducation.

----

So I know the inductive step:

Assume $5$ divides $8^k-3^k$

Show $5$ divides $8^{k+1} - 3^{k+1}$

So, $8^k - 3^k = 5p$, for some integer $p$. This is the inductive hypothesis.

$8^{k+1}-3^{k+1} = \left(8^k\cdot 8 - 3^k\cdot 3\right) = \left(8^k\cdot (5+3) - 3^k\cdot 3\right) = \left(5\cdot 8^k + 3\cdot 8^k\right) - 3^k\cdot 3$

I'm stuck from here. Thanks for the help.
• February 26th 2009, 06:05 PM
arpitagarwal82
$8^{k+1}-3^{k+1} = \left(8^k\cdot 8 - 3^k\cdot 3\right)$

$8(8^k - 3^k) + 5.3^k$
= $5p + 5.3^k$
= $5( p + 3^k)$
hence divisible by 5.