How do prove $12^n - 4^n - 3^n +1$ is divisible by 6 using mathematical induction, where n is integral? So this question is very challenging because normally the bases of the exponents are the same. There are too many different bases for me to successfully subtitue in the assumption (when $n=k$)
I was hoping someone out there will have a super smart elegant solution to this!
Base step: test when n = 1 ...
Assume true for $n = 1$
ie . $12^k - 4^k - 3^k +1 = 6M$, where $m$ is an integer
RTP: also true for $n = k+1$
ie.  $12^{k+1} - 4^{k+1} - 3^{k+1} +1 = 6N$ where $N$ is an integer
LHS: $12^{k+1} - 4^{k+1} - 3^{k+1} +1$
$= 12( 4^k + 3^k  - 1 + 6M) - 4^{k}(4) - 3^{k}(3) +1$ (from assumption)
$= 6(12M) + 12(4^k) + 12(3^k) -12 -4^{k}(4) - 3^{k}(3) +1$
Here is where I break down and go around in circles.
 A: Work mod 3, and put aside induction for now. Note that  $4 \equiv_3 1$, and so for each integer $n$:
$$4^n \equiv_3 1^n = 1.$$
Thus $12^n -4^n -3^n +1 \equiv_3 (0 -1 -0 -1) = 0$.
So this quantity is divible by 3 for each positive integer $n$.
Lets now get back to mod 6 though. So $12^n -4^n -3^n +1$ is divisible by 3. But it is also even so it is divisible by 6 as well.
A: Hint: To prove the claim that $3\mid4^n-1$, notice that
$$4^{k+1}-1=4(4^k-1)+3$$
A: We are going to replace $4^n=12^n-3^n+1-6M$
$\begin{align}12^{n+1}-4^{n+1}-3^{n+1}+1
&=12.12^n-4.4^n-3.3^n+1\\
&=12.12^n-4(12^n-3^n+1-6M)-3.3^n+1\\
&=8.12^n+3^n-3+24M
\end{align}$
$12^n$ and $24M$ are obviously divisible by $6$
Notice $3^n-3=3\times\underbrace{(3^{n-1}-1)}_{\text{even}}$ is also divisible by $6$ so you can finish your induction step.
A: Suppose $6 | 12^{n}-4^{n}-3^{n}+1$ for some $n$.
Then $6| 12(12^{n}-4^{n}-3^{n}+1) = 12^{n+1}-12\cdot4^{n}-12\cdot3^{n}+12=$
$12^{n+1}-3\cdot4^{n+1}-4\cdot3^{n+1}+12.$
Since $3^{m} \equiv 3 \pmod 6$, and $4^{m} \equiv 4 \pmod 6$ for every $m$, we have that
$2\cdot4^{n+1} + 3\cdot3^{n+1}-11 \equiv2+3+1\equiv0\pmod 6.$
Hence, $6|(12^{n+1}-3\cdot4^{n+1}-4\cdot3^{n+1}+12)+(2\cdot4^{n+1} + 3\cdot3^{n+1}-11) = 12^{n+1}-4^{n+1}-3^{n+1}+1$.
