2

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.

user71207
  • 1,543

4 Answers4

1

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.

Mike
  • 20,434
  • 1
    Is there a way to do it without modular arithmetic? It is after all a mathematical induction question – user71207 Nov 21 '20 at 02:39
  • I am sorry @user71207 I have no idea how to use induction per se to solve this--or why it would even be called for. Modular arithmetic is used to solve these--and every solution would have to use this implicitly anyway. – Mike Nov 21 '20 at 02:45
1

Hint: To prove the claim that $3\mid4^n-1$, notice that

$$4^{k+1}-1=4(4^k-1)+3$$

user170231
  • 19,334
1

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.

zwim
  • 28,563
1

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

Derek Luna
  • 2,732
  • 8
  • 19