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.
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}$$
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.$
$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$.
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.
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$
