Hi everyone,

First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

**Question**: Prove by induction on $\displaystyle n$ that, for all positive integers $\displaystyle n$, $\displaystyle 3$ divides $\displaystyle 4^n +5$.

I know where I need to go with this, I think, I'm just stuck on the inductive step:

**Proof**: We use induction on n. If $\displaystyle 3$ divides $\displaystyle 4^n +5$, then $\displaystyle 4^n +5=3q$ for some integer $\displaystyle q$.

Base case: If $\displaystyle n=1$, then $\displaystyle 4^n +5=9=3q$, where $\displaystyle q=3$, proving the base case.

Inductive step: Suppose as inductive hypothesis that $\displaystyle 4^k +5=3q$ for some integer $\displaystyle k$. Then $\displaystyle 4^{k+1} +5=3q$ (by inductive hypothesis).

That's as far as I get. Obviously, $\displaystyle 4^{k+1} +5=4*4^k +5$ by definition, but I get stuck there.

Thanx in advanx!

EDIT: not sure how to add the solved prefix, hope this is an okay ad hoc measure.