Prove that $9^n+4^{n+1}$ is a multiple of $5$ for all $n \in \mathbb{N}$
Proof. So i'm going to prove this by induction. The first case when $n=1$ is trivial since: $$9+16=25,$$ implying $ 5 \mid 25$.
Now we need to show is divisible when $n=k+1$. We will use this later on, but $$9^k+4^{k+1}=5k.$$ The n, $$\begin{align}9^{k+1}+4^{k+2} &= 9 \cdot 9^k+4 \cdot 4^{k+1} \\ &= 9 \cdot 9^k+(9-5) \cdot 4^{k+1} \\ &=9 \cdot 9^k+9 \cdot 4^{k+1} -5 \cdot 4^{k+1} \\ &= 9(9^k + 4^{k+1})-5 \cdot 4^{k+1} \\ &=\underbrace{9(5k)-5 \cdot 4^{k+1}}_{\text{This is where the $5k$ comes in}} \\ &= 5(9k-4^{k+1}),\end{align}$$ thus, the original expression a multiple of $5$.
Is my induction correct?
Edit: I see several answers that took a different approach, all is welcome it really helps me see it in a different way. Thank You!
$\endgroup$ 45 Answers
$\begingroup$Yes your proof is correct, as an alternative note that
$$9^n+4^{n+1}\equiv (-1)^n+(-1)^{n+1}\equiv0 \mod 5$$
$\endgroup$ 2 $\begingroup$By the binomial theorem, $9^n+4^{n+1}=(5+4)^n+4^{n+1}=5a+4^n+4^{n+1}=5a+5\cdot4^n$.
$\endgroup$ 3 $\begingroup$By Induction:
$n=0$: $9^0+4^1=5$ , divisible by $5$.
Hypothesis:
Assume : $9^n+4^{ n+1}$ is divisible by $5$.
Step:
$9^{n+1}+4^{n+2} =9 \cdot 9^{n} +4 \cdot 4^{n+1}=$
$(5+4)9^n +4 \cdot 4^{n+1} =$
$ 5 \cdot 9^n +4(9^n+4^{n+1})=$
$ 5 \cdot 9^n +4\cdot 5c= 5(9^n+4c)$,
where $c \in \mathbb{Z^+}$, since $(9^n+4^{n+1})$
is by hypothesis divisible by $5$,
$\endgroup$ $\begingroup$HINT.-$9^n$ is congruent with $1$ or $9$ modulo $10$ and $4^m$ is congruent with $4$ or $6$ modulo $10$. The integer $9^n+4^{n+1}$always end with $5$.
$\endgroup$ $\begingroup$Or another way: $$9^n + 4^{n+1} = (10-1)^n +(5-1)^{n+1}=10c+(-1)^n + 5d+(-1)^{n+1}=10c+5d = 5e$$
Edit:
Another similar way: $$9^n + 4^{n+1}= 9^n+4\cdot(9-5)^n = 9^n+4(9^n+5c)= (1+4)9^n + 20c = 5e$$
$\endgroup$ 3
