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.

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.
