I have to prove the following statement by induction:
$P(n):5^{3n} + 2^{n+1}$ is a multiple of $3$ for all $n \in \mathbb{N}$
I started with the base case for $n=1$, which is true, and then, by taking $P(n)$ as true, $P(n+1)$ gives me $125 * 5^{3n} + 2 * 2^{n+1}$, and I can't see how to prove that this is a multiple of $3$... any suggestions? Thanks in advance!
Following your argument:
By Induction Hypothesis: $5^{3n}+2^{n+1}=3K$, for some $K\in\mathbb N$, so $5^{3n}=3K-2^{n+1}$. Hence, $$125\cdot 5^{3n}+2\cdot 2^{n+1}=125(3K-2^{n+1})+2\cdot2^{n+1}=125\cdot 3\cdot K-123 \cdot 2^{n-1}.$$ The first sumand is clearly divisible by 3 and the last one also, because $123=41\cdot 3$.
No induction required here – lil' Fermat will do:
$5^3\equiv 2^3\equiv 2\mod 3$, so $$5^{3n}+2^{n+1}\equiv 2^n+2^{n+1}=2^n(1+2)\equiv 0\mod 3.$$
$P(n)$ being true means that $$ 5^{3n}+2^{n+1} = 3k, $$ for some $k \in \mathbb Z$. Now write $$ 125 \cdot 5^{3n} + 2\cdot2^{n+1} = 123 \cdot 5^{3n} + 2 (5^{3n}+2^{3n}) = 3 \cdot 41 \cdot 5^{3n} + 2 \cdot 3k = 3(41 \cdot 5^{3n} + 2k). $$
Notice the following two facts:
$$125 = 5^3 \;\;\; \Rightarrow \;\;\; 125 \cdot 5^{3n} = 5^{3n+3} = 5^{3(n+1)}$$ $$2 \cdot 2^{n+1} = 2^{(n+1)+1} = 2^{n+2}$$
Recall further that you want to show $P(n+1)$ is true, i.e. $3$ divides $5^{3(n+1)} + 2^{(n+1)+1} = 5^{3(n+1)} + 2^{n+2}$.
See how you might continue from there?
Calling $m_3 = 3m$ as a rule, we have
$$ 5^{3n}+2^{n+1}=(126-1)^n +(3-1)(3-1)^n = m_3+(-1)^n+3 (p_3+(-1)^n)-(p_3+(-1)^n) = q_3 + (-1)^n-(-1)^n = q_3\equiv 0 \mod 3 $$
