How to prove that $4^{n} + 5$ is divisible by $3$.

Question

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 1

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