How do I prove $11\mid 2^{6n+1}+3^{2n + 2}$ by induction?

Question

How do I prove by induction that $$11\mid 2^{6n+1}+3^{2n + 2}$$ for all $n\ge 0$.

Any hints or suggestions would be awesome.

Answer 1

If $f(m)=2^{6m+1}+3^{2m+2},$

$f(n+1)=2^{6(n+1)+1}+3^{2(n+1)+2}=2^6\cdot2^{6n+1}+9\cdot3^{2n+2}$

To eliminate $2^{6n+1},$

$f(n+1)-2^6f(n)=3^{2(n+1)+2}-2^6\cdot3^{2n+2}=3^{2n+2}(9-64)=-11\cdot5\cdot3^{2n+2}$

So, $f(n+1)$ will be divisible by $11\iff11\mid f(n)$

Now for the base case $f(0)=?$

We can eliminate $3^{2n+2}$ as well by calculating $f(n+1)-9f(n)$

Answer 2

Hint:
$6(n+1)+2=\underbrace{6n+2}_a+\underbrace{6}_b$
$2(n+1)+2=\underbrace{2n+2}_a+\underbrace{2}_b$
$2^{a+b}=2^a2^b$
$3^{a+b}=3^a3^b$
$64=55+9$
if $x|(y+z)$ and $x|y$ then $x|z.$

Answer 3

Hint (without congruences or induction):

$$2^{6n+1} + 3^{2n+2} = 2 \cdot 8^{2n} + 9 \cdot 3^{2n} = 2 \cdot 8^{2n} + 9 \cdot 3^{2n} = 2 \cdot (11-3)^{2n} + 9 \cdot 3^{2n}$$

In the binomial expansion of $(11-3)^{2n}$ the only term not divisible by $11$ is the last one, so there exists $k \in \mathbb{Z}$ such that $(11-3)^{2n} = 11 \cdot k + 3^{2n}$. Then:

$$2 \cdot (11-3)^{2n} + 9 \cdot 3^{2n} = 2 \cdot 11 \cdot k + (2+9)\cdot 3^{2n} = (2 \cdot k + 3^{2n}) \cdot 11$$

Answer 4

First, show that this is true for $n=0$:

$2^{6\cdot0+1}+3^{2\cdot0+2}=11$

Second, assume that this is true for $n$:

$2^{6n+1}+3^{2n+2}=11k$

Third, prove that this is true for $n+1$:

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

$2^{6n+6+1}+3^{2n+2+2}=$

$2^{6+6n+1}+3^{2+2n+2}=$

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

$64(2^{6n+1})+9(3^{2n+2})=$

$64(2^{6n+1})+(64-55)(3^{2n+2})=$

$64(2^{6n+1})+64(3^{2n+2})-55(3^{2n+2})=$

$64(\color\red{2^{6n+1}+3^{2n+2}})-55(3^{2n+2})=$

$64(\color\red{11k})-55(3^{2n+2})=$

$11(64k)-55(3^{2n+2})=$

$11(64k-5(3^{2n+2}))$

---

Please note that the assumption is used only in the part marked red.