How to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction?

Question

I want to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction. My first step is replace $n$ with $1$.

1. $2^{1+2}+3^{2(1)+1}$
2. $2^3+3^3$
3. $8+27$
4. $35 = 7\times 5$

The next step is assume that $2^{n+2}+3^{2n+1}$ is divisible by 7. And the last step is to prove that $2^{(n+1)+2}+3^{2(n+1)+1}$.

1. $2^{(n+1)+2}+3^{2(n+1)+1}$
2. $2^{n+3}+3^{2n+3}$
3. I got stuck here.

How can I prove it using induction?

Answer 1

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

Answer 2

Hint:

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

Answer 3

Let $$f(n)=2^{n+2}+3^{2n+1}$$ so that $$f(n+1)=2^{n+3}+3^{2n+3}$$

Then

$$ \begin{align} f(n+1)-f(n) &= 2^{n+3}+3^{2n+3}-2^{n+2}-3^{2n+1} \\ &= 2^{n+2} \left(2-1 \right)+3^{2n+1}\left(3^2 - 1 \right) \\ &= 2^{n+2} + 8\left(3^{2n+1}\right) \\ &= 2^{n+2} + 3^{2n+1} + 7\left(3^{2n+1}\right) \end{align} $$

We assumed that $2^{n+2} + 3^{2n+1} ~|~ 7$ and $7\left(3^{2n+1}\right)$ is obviously divisble by 7. So we're done.

Answer 4

Intuitively $ $ the induction step arises by applying the Congruence Product Rule (see below)

$$ \begin{align}{\rm mod}\,\ 7\!:\qquad \color{#0a0}{3^2}\ \equiv&\,\ \ \color{#0a0}{2}\\[2pt] 3^{1+2n}\equiv&\,\ {-}2^{2+n}\qquad\ {\rm i.e.}\ \ P(n)\\[-4pt] \overset{\rm multiply}\Rightarrow\ \ 3^{1+2n}\,\color{#0a0}{3^2} \equiv&\,\ {-}2^{2+n}\, \color{#0a0}{2}\\[2pt] {\rm i.e.}\quad\, \ 3^{1+2(\color{#c00}{n+1})}\equiv&\,\ {-}2^{2+(\color{#c00}{n+1})}\ \ \ {\rm i.e.}\ \ P(\color{#c00}{n\!+\!1})\end{align}\ \qquad $$

If we eliminate the language of congruences by substituting inline the below proof of the Congruence Product Rule then we obtain exactly the common proof given in most other answers. Even if congruences are unfamiliar, we can still impose this intuitive arithmetical structure by using the Product Rule in an equivalent divisbility form, namely

$$\begin{align} {\rm mod}\,\ m\!:\, A\equiv a,\, B\equiv b&\ \ \,\Longrightarrow\,\ \ AB\equiv ab\qquad\text{Congruence Product Rule}\\[3pt] m\mid A-a,\ B-b&\,\Rightarrow\, m\mid AB-ab\qquad\text{Divisibility Product Rule}\\[4pt] {\bf Proof}\quad (A-a)B+a(B&-b)\, = AB-ab\end{align}$$

Thus the inductive step need not be pulled out of a hat like magic. Rather, it has intuitive arithmetical content as congruence multiplication. See here for further discussion.

Note: I wrote the congruence proof in the above form (vs. simpler congruence forms) in order to better highlight how other answers are precisely equivalent to applying the Product Rule.

Answer 5

For $n\geq 1$, you are trying to show that $2^{n+2}+3^{2n+1}=7m$, where $m\in\mathbb{Z}$. You already did the base case.

Fix some $k\geq 1$, and assume that $$ 2^{k+2}+3^{2k+1}=7\ell, \ell\in\mathbb{Z}. $$ To be shown is that $$ 2^{k+3}+3^{2k+3}=7\eta, \eta\in\mathbb{Z}. $$ Start with the left-hand side and work your way to the right hand side, completing the inductive step: \begin{align} 2^{k+3}+3^{2k+3} &= 2\cdot 2^{k+2}+9\cdot 3^{2k+1}\\[0.5em] &= 9(2^{k+2}+3^{2k+1})-7\cdot 2^{k+2}\\[0.5em] &= 9(7\ell)-7\cdot 2^{k+2}\\[0.5em] &= 7(9\ell-2^{k+2})\\[0.5em] &= 7\eta. \end{align} This concludes the proof. I might write it up slightly more formally, but those are the key steps.