Proof by Induction - Algebra Problem (Steps included but not understood)

I do not quite understand this proof, if anyone could explain the steps for me it would be greatly appreciated. It's probably something glaringly obvious I'm not seeing, thanks in advance.

Prove that for every integer $n \ge 0,$ the number $4^{2n+1}+3^{n+2}$ is a multiple of 13.
Proof. We use induction on n, starting with $n=0$
$P(0):4^{2(0)+1}+3^{0+2}=4+9=13=13\cdot1$
Assume $P(k):4^{2k+1}+3^{k+2}=13t$ for some integer $t$. We must prove
$P(k+1): 4^{2(k+1)+1}+3^{(k+1)+2}$ is a multiple of $13$.
We have
$4^{2(k+1)+1}+3^{(k+1)+2}=4^{(2k+1)+2}+3^{(k+2)+1}$
$=4^2(4^{2k+1})+4^2(3^{k+2}-3^{k+2})+3\cdot3^{k+2}$
$=4^2(4^{2k+1}+3^{k+2})+3^{k+2}(-4^2+3)$
$=16\cdot13t+3^{k+2}\cdot(-13)$ (by $P(k)$)
$=13(16t-3^{k+2})$, proven.

• Which steps confuse you? Commented Sep 4, 2014 at 14:48
• In the second step the term $4^2(3^{k+2}-3^{k+3}) = 0$ is put in there to make factoring by grouping work out in the third step. Commented Sep 4, 2014 at 14:53
• Do you know modular arithmetic (congruences), e.g. do you understand $\,16\equiv 3\pmod{13}\,?\,$ If so, I can explain very simply how to discover this proof. Commented Sep 4, 2014 at 15:24

We know something about $4^{2k+1}+3^{k+2}$, but in the expression $$4^2\cdot 4^{2k+1}+3\cdot3^{k+2}$$ we have just $4^{2k+1}$. So we insert a term $4^2\cdot 3^{k+2}$ in order to apply the induction hypothesis. We add nothing provided we subtract the same term: $$4^2\cdot 4^{2k+1}+3\cdot3^{k+2}=4^2\cdot 4^{2k+1}+4^2\cdot 3^{k+2}-4^2\cdot 3^{k+2}+3\cdot3^{k+2}$$ and go on with $$4^2\cdot 13t-3^{k+2}(16-3)$$ which is a multiple of $13$.

A different way of doing the same thing is rewriting the induction hypothesis as $$4^{2k+1}=13t-3^{k+2}$$ and substituting it in the expression for $P(k+1)$: $$4^2\cdot 4^{2k+1}+3\cdot3^{k+2}=4^2(13t-3^{k+2})+3\cdot3^{k+2}.$$

• Thanks everyone for the fast and informative responses, I understand it now. I couldn't understand the rearrangement of the indices in the first step and the zero term being added but it all makes sense now, thanks! Commented Sep 4, 2014 at 15:22

Perhaps the parts that are key are in from the third line to the second line from the end:

$$... \\ =4^2(4^{2k+1}+3^{k+2})+3^{k+2}(-4^2+3) \\ =16\cdot13t+3^{k+2}\cdot(-13)$$

The substitution of $(4^{2k+1}+3^{k+2})$ for $13t$ uses the fact that you assumed the result held for $n=k$. The method of induction requires two parts the way it's done here: (a) $n=0$ holds, and (b) given $n=k$ holds, $n=k+1$ holds.

The other part is in the last line:

$$=13(16t-3^{k+2})$$

after which it's proven. The goal was to show that the expression is divisible by $13$. Since $t,k$ are both integers, the expression is $13 \times$ an integer, which is the same thing as saying the expression is divisible by $13$.

With regard to the grouping you mention in the comments, yes, it's done that way to allow use of the $n=k$ assumption.

Here is a variant on the same idea. $4^{2n+1}+3^{n+2}=4(13+3)^n+9\times 3^n$. Expand the bracket by the binomial theorem. Every term has a factor 13 except $3^n$, so we have that $4^{2n+1}+3^{n+2}$ is a multiple of 13 plus $3^n(4+9)$.

The glaringly obvious looks like the concept of proof by induction itself. To prove a proposition $P(n)$ is true for all $n\geq 0$, it suffices to prove that $P(k) \Rightarrow P(k+1)$ (which is done by assuming $P(k)$, then showing $P(k+1)$, after which you may discharge the assumption and write down $P(k) \Rightarrow P(k+1)$) and that $P(0)$ is true. Using $P(k) \Rightarrow P(k+1)$ we then have $P(0)$ is true therefore $P(1)$ is true. $P(1)$ is true therefore $P(2)$ is true and so on.

• thanks for the edits, i didn't realise math formatting was just tex!
– bob
Commented Sep 4, 2014 at 20:25