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

Question

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.

Answer 1

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}. $$

Answer 2

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.

Answer 3

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)$.

Answer 4

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.