Proof By Induction Divisibility Question: $12\mid 3^n + 7^{n-1} + 8$ Prove that $3^n + 7^{n-1} + 8$ is divisible by $12$ for all positive integers $n$.
I have proved it is true for $n=1$ and I have done the 'assume $n=k$' step, but after getting $3^{k+1} + 7^k + 8$, I am stuck. Where do I go from here?
 A: HINT: $3^{k+1}+7^{k}+8=7(3^{k}+7^{k-1}+8)-4\cdot3^{k}-6\cdot8=7(3^{k}+7^{k-1}+8)-12(3^{k-1}+4)$
Clarification of where this comes from:
$3^{k+1}=3\cdot3^{k}=7\cdot3^{k}-4\cdot3^k$
similarly $8=7\cdot8-6\cdot8$
A: Hint: Show that $3^{k+1}+7^k+8 = 3\cdot\left(3^{k}+7^{k-1}+8\right)+4\cdot \left((3\cdot 2+1)^{k-1}-3-1\right)$ is divisible by $3$ and $4$.
A: Your next step is to relate the expression you have for $k+1$ to the expression for $k$ (no need, incidentally, to change notation from $n$ to $k$)
Since the expression involves powers, you probably need to multiply by something, and $3$ and $7$ are the obvious candidates.
So let $f(k)=3^k+7^{k-1}+8$ then we have $$f(k+1)=3^{k+1}+7^k+8=3f(k)+g(k)$$ where $g(k)$ is to be found by putting in what we know for $f(k)$. We know that $12|f(k)$ and if we can prove that $12|g(k)$ we are done.
This knocks out the power of $3$, but doesn't immediately get you the whole way. But go confidently, one step at a time. 
A: It might be easier to split into the two cases: $\pmod 3$ and $\pmod 4$ then combine using the Chinese Remainder Theorem.
I.e., we prove:

$3^n+7^{n-1}+8 \equiv 0 \pmod 4$ for all $n \geq 1$

and

$3^n+7^{n-1}+8 \equiv 0 \pmod 3$ for all $n \geq 1$.

