induction - 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.

Answer

From @JMoravitz and continuing from the question above,

$4 * 4^{n} + 5$

$(3 + 1)4^{n} + 5$

$3(4^{n}) + (4^{n} + 5)$

From the base case, we know $(4^{n} + 5)$ is divisible by 3, and trivially $3(4^{n})$ is also divisible by 3.

$Q.E.D.$