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.
 A: No need for induction:
$$\begin{align}5+4^n&=5+(3+1)^n\\
&=5+\sum_{k=0}^n\binom{n}{k}3^k\\
&=5+1+\sum_{k=1}^n\binom{n}{k}3^k\\
&=3\cdot\left(2+\sum_{k=1}^n\binom{n}{k}3^{k-1}\right).
\end{align}$$
A: 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.$
A: $4\cdot 4^n+5=4(4^n+5)-15$ and both $4^n+5,15$ are divisible by $3$.
A: It is $$4^n+5\equiv 1^n+2\equiv 1+2\equiv 0 \mod 3$$
A: $4^n +5 \equiv 4^n - 1$ mod $3$. 
$4^n-1 = (2^n - 1)(2^n + 1)$. Either $2^n - 1$, or $2^n + 1$ is divisible by $3$, because among three successive integers (in this case $2^n-1, 2^n, 2^n + 1$) exactly one of them is divisible by $3$, and clearly, $2^n$ is not one of them.
More specifically, if $n$ is odd, then $2^n + 1$ is divisible by $3$, otherwise $2^n - 1$ is divisible by $3$.
A: You may use mathematical induction to solve this easily.
Let us assume $4^n+5=3k$
$$4^{n+1}+5=4{\cdot}4^{n}+5$$
$$=4{\cdot}4^{n}+20-15$$
$$=4(4^{n}+5)-15$$
$$=4(3k)-3{\cdot}5$$
$$=3(4k-5)$$
$$=3m$$
Hence $4^n+5$ is divisible by 3 for all n.
A: 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$
