prove that for every natural n, $5^n - 2^n$, can be divided by 3

Question

How to prove, using recursion, that for every natural n:$$5^n - 2^n$$ can be divided by 3.

Answer 1

1. setting $n=1$, $\implies 5^1-2^1=3$ is divisible by $3$

Thus, the number $5^n-2^n$ is divisible by $3$ for $n=1$

2. assume for $n=k$, the number $5^n-2^n$ is divisible by $3$ then $$\color{blue}{5^k-2^k=}\color{blue}{3m}$$ where, $m$ is some integer

3. setting $n=k+1$, $$5^{k+1}-2^{k+1}=5\cdot 5^k-2\cdot 2^k$$ $$=5\cdot 5^k-5\cdot 2^k+3\cdot 2^k$$ $$=5(\color{blue}{5^k-2^k})+3\cdot 2^k$$ $$=5(\color{blue}{3m})+3\cdot 2^k$$ $$=3(5m+2^k)$$ since, $(5m+2^k)$ is an integer hence, the above number $3(5m+2^k)$ is divisible by $3$

Hence, $5^n-2^n$ is divisible by $3$ for all integers $n\ge 1$

Answer 2

Hint: $(x-y)\,|\,(x^n-y^n)$ for all $x,y$

Answer 3

Since $5\equiv 2\pmod 3$, you get $5^n\equiv 2^n\pmod 3$.

---

Or use the binomial formulas $$ A^n-B^n=(A-B)(A^{n-1}+A^{n-2}B+…+B^{n-1}) $$

---

Or use the binomial theorem $$ 5^n=(2+3)^n=2^n+n2^{n-1}·3+\binom n2 2^{n-2}·3^2+…+3^n $$

Answer 4

Hint $a^n-b^n=(a-b)((a)^{n-1}+...+b^{n-1})$ from general terms of binomial $(a-b)^n$

Answer 5

In using recursion, we can consider the following:

It holds for $n=1$.

Suppose it holds for some $n\geq 1$, that is $5^n-2^n=3k$ for some integer $k$, then $5^{n+1}-2^{n+1}=3\cdot 5^n+2\cdot 5^n-2\cdot 2^n=3(5^n+2\cdot 3k)$.

Hence, by recursion, the result follows.

Answer 6

It clearly holds for $n=1$. Suppose it holds for some $k$.

$5^{k+1} - 2^{k+1} = 5^k(5-2) + 2(5^k - 2^k)$. $3$ goes into both terms, so it holds for $k+1$. QED.