Strategy for solving $7\vert2^{n+2}+3^{2n+1}$ by induction.

Question

So I have to show the following to be true using induction

$7\mid 2^{n+2}+3^{2n+1}$

This is easily checked with the case $n=0$ because $7 \mid 7$, but I assuming this holds for$n=k :$ $$7\mid 2^{k+2}+3^{2k+1}$$

I fail to see how I can use this for $n=(k+1):$ $$\begin{align*}\begin{split} &7 \mid \left(2^{k+3}+3^{2k+3}\right) &\Longleftrightarrow\\ &7 \mid \left(2\times2^{k+2}+3^2\times3^{2k+1}\right) \end{split}\end{align*} $$

I'm assuming my strategy is flawed, but it's a while since I've done these and I can't remember what should be done.

Answer 1

$2\times2^{k+2}+3^2\times3^{2k+1}=2\times(2^{k+2}+3^{2k+1})+7\times3^{2k+1}$

Answer 2

let $T_n=2^{n+2}+3^{2n+1}$ then we have $T_{n+1}=2^{n+3}+3^{2n+3}$ and we get after some algebra $T_{n+1}-T_n=T_n+3^{3n+1}\cdot 7$ from here we have $T_{n+1}=2T_n+7\cdot 3^{3n+1}$ since $7|T_n$ and $|7\cdot 3^{2n+1}$ we get $7|T_{n+1}$

Answer 3

You checked it for $n=0$, so now you have to prove implication: $$ \left(\forall n \in \mathbb{N}\right)\left(\underbrace{7 \mid 2^{n+2} + 3^{2n+1}}_{\mathrm{Assumption}} \Longrightarrow \underbrace{7 \mid 2^{(n+1)+2} + 3^{2(n+1)+1}}_{\mathrm{Thesis}}\right)$$

Simple thesis transformation:

$$\begin{align*}\begin{split} 2^{(n+1)+2} + 3^{2(n+1)+1} &= 2^1 \cdot 2^{n+2} + 3^2 \cdot 3^{2n+1}\\ &= 2 \cdot 2^{n+2} + 9 \cdot 3^{2n+1}\\ &= 2 \cdot 2^{n+2} + (2+7) \cdot 3^{2n+1}\\ &= \left(2 \cdot 2^{n+2} + 2\cdot 3^{2n+1}\right) + 7 \cdot 3^{2n+1}\\ &=2\cdot\left(2^{n+2} + 3^{2n+1} \right) + 7 \cdot 3^{2n+1} \end{split}\end{align*}$$

From assumption $(\exists k \in \mathbb{Z})(2^{n+2} + 3^{2n+1} =7k)$, so $$\begin{align*}\begin{split} 2^{(n+1)+2} + 3^{2(n+1)+1} &= 2\cdot\left(2^{n+2} + 3^{2n+1} \right) + 7 \cdot 3^{2n+1}\\ &= 2 \cdot 7k + 7 \cdot 3^{2n+1} \\ &= 7 \cdot \left(2\cdot k + 3^{2n+1}\right) \end{split}\end{align*}$$

$$7 \mid \left(7 \cdot \left(2\cdot k + 3^{2n+1}\right) \right) \Longleftrightarrow 7 \mid \left(2^{(n+1)+2} + 3^{2(n+1)+1}\right)$$ Which proves the inductive thesis, and we obtain $\left(\forall n \in \mathbb{N}\right)\left(7 \mid 2^{n+2} + 3^{2n+1} \right)$.