Induction for divisibility: $3\mid 12^n -7^n -4^n -1$ I must use mathematical induction to show that 
$a_{n} = 12^n −7^n −4^n −1$ is divisible by 3 for all positive integers n.

Assume true for $n=k$
$a_{k} = 12^k -7^k -4^k -1$
Prove true for $n=k+1$
$a_{k} = 12^{k+1} -7^{k+1} -4^{k+1} -1$
$ = (12^k)(12) - (7^k)(7) - (4^k)(4) -1$
$ = (12^k)(12) - (7^k)(3+4) - (4^k)(3+1) -1$

I'm not really sure about the last step, as someone just told me to do it. Am I supposed to find the right addends to use and then distribute the exponent terms until I get a multiple of the original $a_{k}$? Because I can't get it to work out evenly, and the -1 at the end gives me trouble. Also, I know that $12^n$ is a multiple of three already, but I don't know how to implement that fact to my advantage. Can I prove that $7^{n}-4^{n}-1$ is also a multiple of three and go from there?
 A: $$a_{k+1}-7a_k=12^k(12-7)+4^k(7-4)\equiv0\pmod3$$
$$\implies a_{k+1}\equiv7a_k\pmod3$$
So, $3|a_{k+1}\iff3|a_k$
We can try with $a_{k+1}-4a_k$ as well.
A: First, show that this is true for $n=1$:
$12^1−7^1−4^1−1=0$
Second, assume that this is true for $n$:
$12^n−7^n−4^n−1=3k$
Third, prove that this is true for $n+1$:
$12^{n+1}−7^{n+1}−4^{n+1}−1=$
$\color\red{12^n−7^n−4^n−1}+11\cdot12^n-6\cdot7^n-3\cdot4^n=$
$\color\red{3k}+11\cdot12^n-6\cdot7^n-3\cdot4^n=$
$3k+11\cdot12\cdot12^{n-1}-6\cdot7^n-3\cdot4^n=$
$3k+132\cdot12^{n-1}-6\cdot7^n-3\cdot4^n=$
$3(k+44\cdot12^{n-1}-2\cdot7^n-1\cdot4^n)$

Please note that the assumption is used only in the part marked red.
A: Hint $\ $ incrementing $\,n\,$ doesn't change the summands $ $ mod $\,3,\ $ i.e.
$$ 4^{n+1} = 4^n + 3\cdot 4^n\equiv 4^n$$
$$ 7^{n+1} = 7^n + 6\cdot 7^n\equiv 7^n$$
$$ 12^{n+1} \equiv 12^n \equiv 0\ \ {\rm by}\ \ n\ge 1$$
A: Hint: Instead of the last step, I would do this:
\begin{align*} a_{k+1} &= 12^{k+1} -7^{k+1} -4^{k+1} -1 \\
 &= 12^k \cdot 12 - 7^k \cdot 7 - 4^k \cdot 4 - 4 + 3 \\
 &= 12^k \cdot 8 - 7^k \cdot 3 + 4(12^k-7^k-4^k-1)+3 \end{align*}
A: Since $(x-12)(x-7)(x-4)(x-1)=x^4-24x^3+183x^2-496x+336$, we have that
$a_n=12^n-7^n-4^n-1$ satisfies
$$
a_n=24a_{n-1}-183a_{n-2}+496a_{n-3}-336a_{n-4}\tag{1}
$$
Since the first $4$ values
$$
a_1=0,a_2=78,a_3=1320,a_4=18078\tag{2}
$$
are all divisible by $6$, induction with $(1)$ and $(2)$ insure that $6\mid a_n$ for all $n\ge1$.
