2
$\begingroup$

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$.

So far I have the base case completed, and believe I am close to completing the proof itself.

Base case:$(n=1)$

$3^1 + 7^1 - 2 = 8/8 = 1 $

Inductive Hypothesis: Assume that $3^n +7^n −2$ is divisible by 8 for all positive integers n.

Induction step $(n+1)$ case:

$$ 3^{n+1} + 7^{n+1} - 2 $$

$$3(3^{n}) + 7(7^{n}) - 2$$

$$3^n + 7^n = 8x $$

-It seems to me that this could be the end of the proof because whatever the answer is would be a multiple of 8: but I am unsure, any help is appreciated.

$\endgroup$
  • 1
    $\begingroup$ Beware that $3+7-2\neq 1$... $\endgroup$ – Balloon Dec 5 '15 at 22:16
  • $\begingroup$ If $n$ is odd, then $3^n+7^n\equiv 3+7\equiv 2\pmod{8}$. If $n$ is even, then $3^n+7^n\equiv 1+1\equiv 2\pmod{8}$. $\endgroup$ – user236182 Dec 7 '15 at 3:59
5
$\begingroup$

It holds for $n=1,2$.

If it holds for $1,2,\dots,n$, then

\begin{align} &3^{n+1}+7^{n+1}-2\\ &=3^2\cdot3^{n-1}+7^2\cdot7^{n-1}-2\\ &=(8+1)\cdot3^{n-1}+(48+1)\cdot7^{n-1}-2\\ &=8\cdot(3^{n-1}+6\cdot7^{n-1})+3^{n-1}+7^{n-1}-2\\ \end{align} Therefore it also holds for $n+1$.

So it holds for all $n\in \mathbb N$.

$\endgroup$
  • $\begingroup$ Note: since your induction goes back two, you need to remark that it also holds for $n=0$ (which is obvious, but still). $\endgroup$ – lulu Dec 5 '15 at 22:22
  • $\begingroup$ @lulu You're right.. I added $n=2$. $\endgroup$ – Kay K. Dec 5 '15 at 22:24
2
$\begingroup$

We have that $3^n+7^n-2=8k$ for some $k$. Now we substitute this expression into $3(3^n)+7(7^n)-2$ to get:
$3(8k-7^n+2)+7(7^n)-2=24k+4(7^n)+4=24k+4(7^n+1)$ where $7^n+1$ is even so we may rewrite $24k+4(7^n+1)=24k+4(2m)=24k+8m$ which is divisible by $8$.

$\endgroup$
  • 2
    $\begingroup$ You mean $3^n+7^n$, not $3^n+8^n$. $\endgroup$ – marty cohen Dec 5 '15 at 22:25
  • $\begingroup$ I do yes. Thank you. I have edited accordingly. $\endgroup$ – user293794 Dec 5 '15 at 22:27
0
$\begingroup$

$\begin{array}\\ 3^{n+1}+7^{n+1}-2 &=3^{n+1}-1+7^{n+1}-1\\ &=(3-1)\sum_{k=0}^n 3^k+(7-1)\sum_{k=0}^n 7^k\\ &=\sum_{k=0}^n (2\ 3^k+6\ 7^k)\\ &=\sum_{k=0}^n (6\ 3^k+6\ 7^k-4\ 3^k)\\ &=\sum_{k=0}^n (6(3^k+7^k-2)+12-4\ 3^k)\\ &=\sum_{k=0}^n (6(3^k+7^k-2)+4(3-3^k))\\ \end{array} $

Since $3-3^k$ is even for $k \ge 0$ (being the difference of two odd numbers), $4(3-3^k)$ is divisible by $8$.

Therefore, if $3^k+7^k-2$ is divisible by $8$ for $0 \le k \le n$, then $3^{n+1}+7^{n+1}-2$ is also divisible by $8$.

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