# Proof

• Feb 26th 2008, 05:00 AM
bobak
Proof
Quote:

Prove by induction that

$\displaystyle 2( 4^{2n+1}) + 3^{3n+1}$
is divisible by 11 $\displaystyle \forall n \! \in \! \mathbb{N}$
..
• Feb 26th 2008, 06:57 AM
kalagota
are you sure?
for n = 1, $\displaystyle 4^{2(1)+1} + 3^{3(1)+1} = 4^3 + 3^4 = 145$
• Feb 26th 2008, 07:28 AM
bobak
Sorry the latex was a bit confusing, I cleaned it up.
• Feb 26th 2008, 07:40 AM
PaulRS
Ok, let's assume it holds for n, we'll now show it does so for n+1

$\displaystyle a_{n}=2\cdot{4^{2n+1}}+3^{3n+1}$ is divisible by 11

$\displaystyle a_{n+1}=2\cdot{4^{2n+3}}+3^{3n+4}$

$\displaystyle a_{n}-2\cdot{4^{2n+1}}=3^{3n+1}$ then $\displaystyle 3^{3}\cdot(a_{n}-2\cdot{4^{2n+1}})=3^{3n+4}$

So: $\displaystyle a_{n+1}=2\cdot{4^{2n+3}}+27\cdot{a_{n}}-54\cdot{4^{2n+1}}$

Since $\displaystyle 2\cdot{4^{2n+3}}-54\cdot{4^{2n+1}}=2\cdot{4^{2n+1}}\cdot{(16-27)}=-2\cdot{4^{2n+1}}\cdot{11}$ (divisible by 11)

and $\displaystyle a_{n}=2\cdot{4^{2n+1}}+3^{3n+1}$ is divisible by 11

It follows that $\displaystyle a_{n+1}=2\cdot{4^{2n+3}}+3^{3n+4}$ is also divisible by 11