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

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.

• Beware that $3+7-2\neq 1$... – Balloon Dec 5 '15 at 22:16
• 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}$. – user236182 Dec 7 '15 at 3:59

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

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

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

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

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