# Induction exercise check-up

Prove by induction on $n$ that $13$ divides $2^{4n+2} + 3^{n+2}$ for all natural $n$.

For base case it is divisble by 13, and

$2^{4n+6} + 3^{n+3}$ must be divisble too.

$16 * 2^{4n+2}+ 3* 3^{n+2}$

If we denote $2^{4n+2} + 3^{n+2}$ as some $13y$,

we have $3*13y + 13*2^{4n+2}$

Didn't I make a mistake in assuming that $2^{4n+2} + 3^{n+2}$ is divisble by 13? In induction we have to prove that if something is divisible/whatever by something then n+1 is divisible too which I did

• There's no problem with that, but I'll sugest to be a little more explicit. Anyway it's good – Diego Robayo Feb 14 '15 at 12:20
• This doesn't look like a proof-by-induction. Where does that "$2^{4n+6}+3^{n+3}$ must be divisible too" come from? – barak manos Feb 14 '15 at 12:21

Below I expain the innate arithmetical structure that lies at the heart of this sort of inductive proof. This viewpoint allows us to easily see that the usual inductive proof is just a special case of the Congruence Product Rule. Further, it allows is to quickly and easily transform the induction into the trivial induction that $\, 1^n\equiv 1.\,$

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

$$\begin{eqnarray} {\rm mod}\ 13\!:\quad\ \ \color{#c00}{16} &\equiv& \color{#c00}3\\ \color{#0a0}{4\cdot 16^{\large k}}&\equiv& \color{#0a0}{-9\cdot 3^{\large k}},\quad\ \ \ {\rm i.e.}\ \ \ P(k)\\ \Rightarrow\ \ 4\cdot 16^{\large (k+1)} &\equiv& \ \color{#0a0}{4\cdot {16^{\large k}}}\cdot \color{#c00}{16}\\ &\equiv& \color{#0a0}{-9\cdot 3^{\large k}}\cdot\, \color{#c00}3\ \ \ \rm by\ \ \ CPR \\ &\equiv& {-9}\cdot 3^{\large k+1},\,\ \ {\rm i.e.}\ \ \ P(k+1) \end{eqnarray}\qquad$$

by CPR = Congruence Product Rule $\ \color{#c00}{A\equiv a},\ \color{#0a0}{B\equiv b}\,\Rightarrow\, AB\equiv ab.\,$ If congruence arithmetic is unfamiliar it can be eliminated by unwinding the proof of the Product Rule, yielding

$\ \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\\ 13\,\mid\, \color{#c00}{16}&\color{#c00}-&\color{#c00}3, && \color{#0a0}{4\cdot 16^{k}}\!\!\!&\color{#0a0}+&\! \color{#0a0}{9\cdot 3^{k}}\!\!\! &\Rightarrow&\!\! 13\mid 4\cdot 16^{k+1}\!+9\cdot 3^{k+1}\!\!\!\! &=&\!\! 3(\color{#0a0}{4\cdot 16^{k}\!+9\cdot 3^{k}}) \!\!\!&+&\!\! (\color{#c00}{16\!-3})4\cdot 16^{k}\phantom{I^{I^I}} \\ \end{eqnarray}$

The prior is precisely the standard 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. Note $\,P(k)\,$ is $\,4\cdot 16^k\equiv -9\cdot 3^k\equiv 4\cdot 3^k\$ so $\,P(k\!+\!1)$ arises simply by multiplying by $\,16\equiv 3\$ to get $\, P(k\!+\!1)\!:\ 4\cdot 16^{k+1}\equiv 4\cdot 3^{k+1}.\,$ Even more clearly, by dividing, we see that $\,P(k)\,$ is equivalent to $\,(16/3)^k\equiv 1.\,$ But $\,16\equiv 3\,$ so $\,16/3\equiv 1,\,$ so the induction boils down to the trivial induction that $\,1^k\equiv 1,\,$ which is a simple special case of the inductive proof of the Congruence Power Rule.

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 caculus.

Your proof isn't wrong per se, but the wording is a bit confusing (and I would probably end up taking a point or two off if I were grading it). Here's how I would write it:

For $n=0$, $$2^{4\cdot0+2}+3^{0+2} = 2^2 + 3^2 = 13.$$ Now assume that $13|(2^{4n+2}+3^{n+2})$ for some integer $n\geqslant0$. Then $2^{4n+2}+3^{n+2}=13k$ for some integer $k$, and $$2^{4(n+1)+2}+3^{(n+1)+2} = 2^4\cdot2^{4n+2}+3\cdot3^{n+2}=16(2^{4n+2}+3^{n+2})-13\cdot3^{n+2}=13(16k - 3^{n+2})$$ You could also factor it into $$3(2^{4n+2}+3^{n+2}) + 13\cdot2^{4n+2}= 13(3k + 2^{4n+2}).$$

• Remark that the equation used in the inductive step is precisely the equation used in the proof of the Congruence Product Rule, namely it is the second line below (see my answer). – Bill Dubuque Feb 14 '15 at 16:37
• $\ \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\\ 13\,\mid\, \color{#c00}{2^4}&\color{#c00}-&\color{#c00}3, && \color{#0a0}{2^{4n+2}}\!\!\!&\color{#0a0}+&\!\! \color{#0a0}{3^{n+2}}\!\!\! &\Rightarrow&\!\! 13\mid 2^{4(n+1)+3}\!+3^{(n+1)+2}\!\!\!\! &=&\!\! 2^4(\color{#0a0}{2^{4n+2}\!+3^{n+2}}) \!\!\!&+&\!\! (\color{#c00}{2^4\!-3})(-3^{n+2})\phantom{I^{I^I}} \\ \end{eqnarray}$ – Bill Dubuque Feb 14 '15 at 16:37
• i.e. it is $\ \color{#c00}{2^4\equiv 3},\ \color{#0a0}{2^{4n+2}\equiv - 3^{n+2}}\,\Rightarrow\, 2^4 2^{4n+2}\equiv -3\cdot 3^{n+2}\pmod{13}$ – Bill Dubuque Feb 14 '15 at 16:38

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

$2^{4+2}+3^{1+2}=13\cdot7$

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

$2^{4n+2}+3^{n+2}=13k$

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

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

$2^4\cdot2^{4n+2}+3^1\cdot3^{n+2}=$

$16\cdot2^{4n+2}+3\cdot3^{n+2}=$

$(13+3)\cdot2^{4n+2}+3\cdot3^{n+2}=$

$13\cdot2^{4n+2}+3\cdot2^{4n+2}+3\cdot3^{n+2}=$

$13\cdot2^{4n+2}+3\cdot(\color{red}{2^{4n+2}+3^{n+2}})=$

$13\cdot2^{4n+2}+3\cdot\color{red}{13k}=$

$13\cdot2^{4n+2}+13\cdot3k=$

$13\cdot(2^{4n+2}+3k)$

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

your assumption is necessary in the induction the steps of induction is : 1. calculate when n = 1 it is true or not 2. assume when n = k is true then check whether n = k + 1 is also true.

1. for n = 1,

$2^{4n+2}+3^{n+2} = 2^6+3^3 = 7*13$

1. assume $2^{4k+2}+3^{k+2}$ is divisible then

$2^{4(k+1)+2}+3^{(k+1)+2}$

$=2^{4k+6}+3^{k+3}$

$=16*2^{4k+2}+3*3^{k+2}$

$=3*(2^{4k+2}+3^{k+2})+13*2^{4k+2}$

$=13x$ for some real x

So for all natural n, $2^{4k+2}+3^{k+2}$ is divisible by 13. Q.E.D.

HINT:

If $f(n)=2^{4n+2}+3^{n+2}$

$f(m+1)-3f(m)=2^{4(m+1)+2}+3^{(m+1)+2}-3[2^{4m+2}+3^{m+2}]=2^{4m+2}(2^4-3)$ which is divisible by $13$

So, $13|f(m+1)\iff13|f(m)$

Alternatively try with $f(m+1)-2^4f(m)$