# Simple Proof by Induction

• March 2nd 2011, 09:21 PM
demode
Simple Proof by Induction
Using mathematical induction I want to show that $3^{6n}-2^{6n}$ is divisible by $35$, $\forall n \in \mathbb{N}$.

The base case n=1 is true: $3^6-2^6=665$, 665/35=19.

Inductive step: Suppose $3^{6k}-2^{6k}$ is divisible by 35 for some $k \in \mathbb{N}$. That means $3^{6k}-2^{6k} = 35m$ for some m. Then

$3^{6(k+1)}-2^{6(k+1)}= 3^{6k}.3^6-2^{6k}.2^6$

Now how can I simplify this to factor out $3^{6k}-2^{6k}$ to show that it's divisible by 35 for k+1?
• March 2nd 2011, 11:18 PM
emakarov
Quote:

Originally Posted by demode
$3^{6(k+1)}-2^{6(k+1)}= 3^{6k}.3^6-2^{6k}.2^6$

Rewrite $2^6$ as $3^6-665$.
• March 2nd 2011, 11:54 PM
FernandoRevilla
Without using induction:

$3^{6(k+1)}-2^{6(k+1)}=(3^6)^{k+1}-(2^6)^{k+1}=$

$(3^6-2^6)[(3^6)^k+(3^6)^{k-1}2^6+\ldots+(2^6)^k]=35h\;(h\in \mathbb{N})$