# Proving that $3^n+7^n+2$ is divisible by 12 for all $n\in\mathbb{N}$.

Can someone help me prove this? :( I have tried it multiple times but still cannot get to the answer.

Prove by mathematical induction for $n$ an element of all positive integers that $3^n+7^n+2$ is divisible by 12.

• On this site, you are supposed to show any work you have done first so people know how to help you. Also you are supposed to learn how to format your question using mathjax. math.meta.stackexchange.com/questions/5020/…
– Arby
Apr 30, 2017 at 1:56
• Prove by mathematical (what?). $3^n \pmod {12}$ goes through a cycle, as does $7^n$. There are not many to try. Apr 30, 2017 at 2:00
• @Arby Thank you for the reminder. Sorry I wasnt sure about the proper procedure to ask questions on this site. Nevertheless I have just included my workings :) thx Apr 30, 2017 at 2:04
• Your final expression is divisible by 12, so you're done... Apr 30, 2017 at 2:04
• @JohnDoe sorry, i forgot to include in the -4(3^k) Apr 30, 2017 at 2:06

Hint:

If $f(n)=3^n+7^n+2,$

find $$f(m+1)-7f(m)=?$$

Clearly, $f(m+1)\equiv f(m)\pmod{12}$ for $m\ge1$

Now establish the base case i.e., for $f(1)$

Here's another hint for the core part of your inductive proof (I am sure there are more elegant ways, but the following seems to work fine): \begin{align} 3^{k+1}+7^{k+1}+2&= 7(3^k+7^k+2)-12-4\cdot3^k & \text{(rewrite)}\\[0.5em] &= 7(12\ell)-12-12\cdot3^{k-1} & \text{(by ind. hyp.)}\\[0.5em] &= 12(7\ell)-12(1+3^{k-1}) & \text{(factor out 12)}\\[0.5em] &= 12(7\ell-1-3^{k-1}) & \text{(factor out 12 again)}\\[0.5em] &= 12\eta. & \text{(desired result)} \end{align}

With induction:

When $n=1$: $3^1+7^1+2=12$ is divisible by $12$. Therefore, we assume that $(3^k+7^k+2)$ is divisible by $12$ for some $k≥1$ (thus, $3^k+7^k+2=12a$ where $a$ is a function of $3$ and $7$). Then, $$3^{k+1}+7^{k+1}+2=3×3^k+7×7^k+2$$ $$=3×3^k+7^k(3+4)+6-6+2$$ $$=3×3^k+3×7^k+6+4×7^k-4$$ $$=3(3^k+7^k+2)+4(7^k-1)$$ $$=3×(12a)+4(7-1)(7^{k-1}+7^{k-2}+⋯+2+1)$$ $$=36a+24(7^{k-1}+7^{k-2}+⋯+2+1)$$ $$=12b$$ where $b$ is also a function of $3$ and $7$.

Thus, $(3^{k+1}+7^{k+1}+2)$ is also divisible by $12$.

• Welcome to MSE. Please use MathJax. Feb 8, 2018 at 21:14

A general rule of thumb for induction is to try to get

$3^{n+1} + 7^{n+1}+2 = somethingtodo with(3^n + 7^n+2) = something to do with(multiple of 12) = multiple of 12$

So $3^{n+1} + 7^{n+1} +2 =$

$3*3^n + 7*7^n + 2=$

$3*3^n + 3*7n + 4*7^n + 2=$

$3(3^n + 7^n) + 4*7^n + 2 =$

$3(3^n + 7^n + 2) - 6 + 4*7^n + 2 =$

$3(multiple of 12) + 4*7^n -4$

so now it's a matter of proving $4*7^n -4$ is a multiple of $12$.

$3(multiple of 12) + 4*7^n -4 =$

$3(multiple of 12) + 4(7^n - 1)=$

$3(multiple of 12) + 4*(7-1)(7^{n-1} + .... + 7 + 1)=$

$3(multiple of 12) + 4*6(7^{n-1} + .... + 7 + 1)=$

$3(multiple of 12) + 24*(7^{n-1} + .... + 7 + 1)=$

$3(multiple of 12) + (multiple of 12)*(7^{n-1} + .... + 7 + 1)=$

$multiple of 12$

....

So to formally put this together.

Base case:

$n = 1$. $3^1 + 7^1 + 2 =12$ is a multiple of $12$.

Inductive case:

Assume $3^n + 7^n + 2 = 12K$ is a multiple of $12$..

Then $3^{n+1}+7^{n+1} + 2 =$

$3*3^n + 3*7^n+ 6 + 4*7^n-4 =$

$3(3^n + 7^n + 2) + 4(7^n - 1)=$

$3(12K) + 4(7-1)(7^{n-1} + ... + 1)$

Let $M = (7^{n-1} + ... + 1)$. It's worth noting that if $n = 1$ then $7^{n-1} + ..... + 1 = 1$. It is important in a proof by induction to not make any assumptions that are not provable for the base $n=1$ case. In this case that $7^{n-1} + .... +1$ actually exists.)

$3(12K) + 4(7-1)(7^{n-1} + ... + 1)=$

$3(12K) + 4*6*M =$

$12[3K + 2M]$

is a multiple of $12$.

Conclusion: $3^n + 7^n + 2$ is a multiple of $12$ for all natural $n$.

• Argh, another zombie thread. Feb 23, 2018 at 0:25

Let $x_n = 3^n+7^n+2$ and $y_n=x_n-2= 3^n+7^n$.

Then $y_{n+2}= 10 y_{n+1} -21 y_n$ and so $x_{n+2}= 10 x_{n+1} -21 x_n +24$.

Since $x_1=12$ and $x_2=60$ are multiples of $12$, so is $x_n$ by induction.