Induction for divisibility: $3\mid 12^n -7^n -4^n -1$

Question

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?

Answer 1

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*}

Answer 2

$$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.

Answer 3

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.

Answer 4

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$.