<s>[INST] 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.
 [/INST] 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)$.
</s>