# Simple Proof by Induction

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

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

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

$\displaystyle 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 $\displaystyle 3^{6k}-2^{6k}$ to show that it's divisible by 35 for k+1?
• Mar 2nd 2011, 11:18 PM
emakarov
Quote:

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

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

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

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