How can I 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

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

Answer 2

$4\cdot 4^n+5=4(4^n+5)-15$ and both $4^n+5,15$ are divisible by $3$.

Answer 3

It is $$4^n+5\equiv 1^n+2\equiv 1+2\equiv 0 \mod 3$$

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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$