<s>[INST] How can I prove that $4^{n} + 5$ is divisible by $3$. I have trying to prove that  $4^{n} + 5$.
I've already proved the base case, so I'm working on the inductive step.
I've done the following:
$4^{n} + 5$
$4^{n+1} + 5$
$4*4^{n} + 5$
But I am unsure where to go from here to prove that it is divisible by 3 since I am unsure how to get a $3$ or multiple of $3$ from this.
 [/INST] You can prove that using induction 
We suppose that $4^n + 5 \equiv 3$ is true
Induction base: $n = 1 \Longrightarrow 4^1 + 5 = 9 \equiv 3$ - true.
Induction transition: let $k = n+1 \Longrightarrow 4^k + 5 = 4^{n+1}+5 = 4 \cdot 4^n + 5 = 3\cdot4^n + 4^n + 5$
$3 \cdot 4^n \equiv 3, \ \ 4^n + 5 \equiv 3$ 
Hence $4^{n+1} + 5\equiv3 \Longrightarrow \ 4^n + 5 \equiv 3$
</s>