Show that $7\mid(3^{2n+1}+2^{n+2})$ for all $n\in\mathbb{N}$ [duplicate]

Prove that the following is true for every $$n∈ℕ$$:

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

I've noticed $$3^{2n+1}+2^{n+2} =3^{2n} \cdot 3+2^{n} \cdot 4.$$

Any suggestions how to continue from there to get something like $$7k$$ for $$k\in\mathbb{N}$$.

Thank you in advance!

• What are your thoughts so far? :) May 26, 2014 at 15:25
• Two options: Induction, or use $3^{2n}=9^n$ and modular arithmetic. May 26, 2014 at 15:28
• Hint: if $a \equiv b (\text{mod } c)$, then we'll have $a^n \equiv b^n (\text{mod } c)$, and $9 \equiv 2 (\text{mod } 7)$. Or you can try proof by induction, it should work too. :) May 26, 2014 at 15:30
• @ThomasAndrews There is also a method using recurrence relations which can be used to find the sequence $k_n$ May 26, 2014 at 15:30
• @MarkBennet What is the difference between recurrence and induction? May 26, 2014 at 15:45

6 Answers

Hint $$\ \ 7\mid\color{#c00}{3^2}\!\color{#c00}-\!\color{#c00}2,\,\ 7\mid\overbrace{\color{#0a0}{3^{2k+1}}\!\color{#0a0}+\! \color{#0a0}{2^{k+2}}}^{\large P(k)} \Rightarrow\, 7\mid 2(\color{#0a0}{3^{2k+1}\!\!+\!2^{k+2}}) + (\color{#c00}{3^2\!-2})3^{2k+1}\! =\, \overbrace{3^{2k+3}\!+2^{k+3}}^{\large P(k+1)}$$

Or $$\!\bmod 7\!:\,\ 3\cdot (\color{#c00}{3^2})^k\!+ 4\cdot 2^k\equiv\, 3\cdot \color{#c00}2^k\! + 4\cdot 2^k\equiv\, 7\cdot 2^k\equiv 0,\,$$ by $$\,\color{#c00}{3^2\equiv 2}$$

The Remark below shows how to derive the first inductive proof from the second modular proof (it shows the inductive proof is precisely a special case of a proof of the Congruence Product Rule).

Or, notice $$\ 2^2\!+2+1 = 7\$$ so we can apply

Lemma $$\ \ a^2\!+a+1\mid a^{n+2}+(a+1)^{2n+1}\! =: b$$

Proof $$\, \ {\rm mod}\,\ a^2\!+a+1\!:\ \color{#0a0}{a(a+1)\equiv -1}$$ and $$\,\color{#c00}{a^3\equiv 1}\$$ by $$\,0\equiv (a\!-\!1)(a^2\!+a+1) = a^3\!-1,\,$$

$$\quad {\rm so}\,\ \ \ a^{2n+1}b = a^{3n+3} + (\color{#0c0}{a(a+1)})^{2n+1} \equiv\, (\color{#c00}{a^3})^{n+1}\!-1\equiv 0\$$ so $$\ b\equiv 0.\ \ \ \bf\small QED$$

Or $$\ a\!+\!1\equiv -a^2\Rightarrow\,(a\!+\!1)^{2n+1}\equiv -a^{4n+2}\equiv -a^{n+2}\$$ by $$\,(\color{#c00}{a^3})^n\equiv \color{#c00}1^n,\,$$ cf. mod order reduction.

Remark $$\$$ Below I explain how the first explicit inductive proof is a special case of the second congruence arithmetic proof, which boils down to $$\color{#0a0}{(-1)^{2n+1}\equiv -1}\,$$ and $$\color{#c00}{1^{n+1}\equiv 1},\,$$ both of which have trivial inductive proofs (a special case of the Congruence Power Rule inductive proof).

Here is the inductive step $$\,P(k)\,\Rightarrow\,P(k\!+\!1)\,$$ written in intuitive congruence arithmetical form

$$\begin{eqnarray} {\rm mod}\ 7\!:\qquad \color{#c00}{3^{\large 2}} &\equiv&\, \color{#c00}2\\[.2em] \times\qquad\quad \color{#0a0}{3^{\large 2k+1}}&\equiv&\, \color{#0a0}{-2^{\large k+2}},\quad\:\!\ {\rm i.e.}\ \ \ P(k)_{\phantom{|}}\\ \hline \Rightarrow\quad \ \color{#c00}{3^{\large 2^{\Large\phantom{|}}}}\: \color{#0a0}{3^{\large 2k+1}} &\equiv&\, \color{#c00}2 (\color{#0a0}{- 2^{\large k+2}})\\[.2em] {\rm i.e.}\quad 3^{\large 2(k+1)+1} &\equiv&\, {-}\!2^{\large k+3},\ \ \ \ \ \ {\rm i.e.}\ \ P(k\!+\!1)\\ \end{eqnarray}\qquad\qquad$$

by the Congruence Product Rule $$\ A\equiv a,\ B\equiv b\,\Rightarrow\, AB\equiv ab.\,$$ If congruence arithmetic is unfamiliar it can be eliminated by unwinding the proof of the Product Rule (or, more conceptually, by using an equivalent Divisibility Product Rule), yielding a proof in divisibility language

$$\quad \begin{eqnarray} 0\,\equiv\, \color{#c00}{A}&\color{#c00}-&\color{#c00}a, &&\ \color{#0a0}{B}&\color{#0a0}-& \color{#0a0}b &\Rightarrow& \qquad AB\ -\ ab &=& a\ \ (\color{#0a0}{\ B\ \ -\ \ b}\ ) &+& (\color{#c00}{A-a})B\,\equiv\, 0\\[.2em] 7\,\mid\, \color{#c00}{3^2}&\color{#c00}-&\color{#c00}2, && \color{#0a0}{3^{2k+1}}\!&\color{#0a0}+&\! \color{#0a0}{2^{k+2}} &\Rightarrow& 7\mid 3^{2k+3}\!+2^{k+3}\! &=& 2(\color{#0a0}{3^{2k+1}\!+2^{k+2}}) &+& (\color{#c00}{3^2\!-2})3^{2k+1}\phantom{I^{I^I}} \\ \end{eqnarray}$$

The prior is precisely the common inductive proof that is usually pulled out of hat like magic, without any intuitive motivation. We can employ further congruence arithmetic to make it even more obvious than above. Notice $$P(k)\,$$ is $$\,3\cdot 9^k\equiv 3\cdot 2^k\,$$ (by $$\:\!{-}4\equiv 3),\,$$ so $$P(k\!+\!1)$$ arises simply by scaling it by $$\,9\equiv 2\$$ to get $$\, P(k\!+\!1)\!:\: 3\cdot 9^{k+1}\!\equiv 3\cdot 2^{k+1}.\,$$ Even more clearly, by dividing by $$\,3\cdot 2^k\,$$ we see that $$P(k)\:\!$$ is equivalent to $$\,(9/2)^k\equiv 1.\,$$ But $$\,9\equiv 2\,$$ so $$\,9/2\equiv 1,\,$$ so the induction proof boils down to the trivial induction that $$1^k\equiv 1,\,$$ which is a trivial special case of the inductive proof of the Congruence Power Rule. See here and this list for more examples like this.

Similarly, many inductions can be transformed into such standard or trivial inductions. Hence it is well-worth the effort to spend some time looking for such innate structure. This is especially true for divisibility problems, since transforming to congruence form allow us to exploit our well-honed arithmetical intuition, which is much stronger than our intuition on divisibility relation calculus.

Note that $2 \equiv 3^2 \pmod 7$, therefore $$3^{2n+1} + 2^{n+2} \equiv 3^{2n+1} + 3^{2n+4} \equiv 3^{2n+1} \cdot 28 \pmod 7,$$ and that is of course divisible by $7$.

\begin{align}3^{2n+1}+2^{n+2}=3\cdot 9^n + 4\cdot 2^n&=7\cdot 9^n -4(9^n-2^n)\\ &=7\cdot 9^n-4(9-2)(9^{n-1}+9^{n-2}\cdot2+\cdots+2^{n-1})\\ &=7[ 9^n-4(9^{n-1}+9^{n-2}\cdot 2\cdots+2^{n-1})]\end{align}

Which is divisible by $7$

Here is a solution based on congruences,

$$3\cdot 9^n +4\cdot 2^n \equiv 3\cdot 2^n +4\cdot 2^n \equiv 7\cdot 2^n \equiv 0\text{(mod 7)}$$

• Thank you. I was closer to the first method. I tried rewriting $3$ to $(7-4)$ and $4$ to $(7-3)$, whereas I should only rewrite $3$ to $(7-4)$ and leave alone the number $4$. I wonder when I would figure that out on my own. May 26, 2014 at 15:42

We have

$$3^{2n+1}+2^{n+2}=3\times\color{red}9^n+4\times2^n\equiv3\times\color{red}2^n+4\times2^n=7\times2^n\equiv0\mod7$$

Note that a sequence with form $u_n=a\cdot 9^n+b\cdot 2^n$ satisfies a linear recurrence with auxiliary equation $$(x-9)(x-2)=0$$ so that $$u_{n+1}=11u_n-18u_{n-1}$$

Hence if $7|u_n \& 7|u_{n-1}$ then $7|u_{n+1}$. We have $u_0=7, u_1=35$ both divisible by $7$, so with a base case established we are done by induction.

If $u_n=7k_n$, then $k_n$ satisfies the same recurrence with $k_0=1, k_1=5$

Just surprised that the very crude induction method with $u_n=3\cdot 9^n+4\cdot 2^n$ hasn't been posted yet - it goes $$u_{n+1} = 3\cdot 9^{n+1}+4\cdot 2^{n+1}=7\cdot3\cdot 9^n+2\cdot 3\cdot 9^n+2\cdot 4\cdot 2^n=7\cdot 3\cdot 9^n+2\cdot u_n$$ which is divisible by $7$ if $u_n$ is divisible by $7$. Base case is $u_0=7$. It depends on the fact that $9-2$ is divisible by $7$.