3
$\begingroup$

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.

Here is my working.. after that last line, i got stuck😭

$\endgroup$
7
  • 2
    $\begingroup$ 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/… $\endgroup$
    – Arby
    Apr 30, 2017 at 1:56
  • 2
    $\begingroup$ Prove by mathematical (what?). $3^n \pmod {12}$ goes through a cycle, as does $7^n$. There are not many to try. $\endgroup$ Apr 30, 2017 at 2:00
  • $\begingroup$ @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 $\endgroup$ Apr 30, 2017 at 2:04
  • 2
    $\begingroup$ Your final expression is divisible by 12, so you're done... $\endgroup$
    – John Doe
    Apr 30, 2017 at 2:04
  • $\begingroup$ @JohnDoe sorry, i forgot to include in the -4(3^k) $\endgroup$ Apr 30, 2017 at 2:06

5 Answers 5

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Argh, another zombie thread. $\endgroup$
    – fleablood
    Feb 23, 2018 at 0:25
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.