<s>[INST] Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$ Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$
Step 1: Show that the statement is true for n = 1:
$4^{2 \cdot 1} + 4 = 20$
Since $20~|~20$, the base case is completed.
Step 2: Show that if the statement is true for n = p, it is true for n = p + 1:
The general idea I had here was to try to get $4^{2(p+1)} + 4$ to look like the original statement, perhaps multiplied with a factor or a sum where each group of terms were divisible by 20.
$4^{2(p+1)} + 4 = 4^{2p+2} + 4$
By one of the exponential rules, we have:
$4^{2p+2} + 4 = 4^{2p} \cdot 4^{2} + 4$
At this point, we could use one of the 16 powers of 4 and together with the 4 term and show that this was divisible by 20, but there does not seem to be any clear reason why $20~|~4^{2p} \cdot 15$. The number $4^{2p}$ always have an even exponent and $4 \cdot 5 = 20$, but not sure how to proceed from here. Any suggestions?
 [/INST] We assume that it is true for $n=p$, then $20|4^{2p} + 4$ so we can write $4^{2p} + 4$ as a product of 20 times an integer say, n, i.e. $4^{2p} + 4=20n$. Then,
$$4^2 (4^{2p} + 4)= 4^2 (20n) \\ 4^{2(p+1)} + 4^3 =4^2 (20n) \\  4^{2(p+1)} + (64 -60) +60 =4^2 (20n) \\ 4^{2(p+1)} +4 = 20 \cdotp 16 \cdotp n -60 \\ 4^{2(p+1)} +4 =20(16n-3)$$
and since $16n-3$ is an integer, then $20| 4^{2(p+1)} +4$, which completes the proof by induction.
</s>