0
$\begingroup$

How can I show/solve this? I've tried by using the basis step and the inductive step, but just can't seem to get it right.

$$\forall(n \geq 0)(4\mid(9^n − 5^n)).$$

$\endgroup$
  • 2
    $\begingroup$ do you mean $9^n-5^n$ by any chance? $\endgroup$ – lab bhattacharjee Apr 25 '13 at 14:58
  • $\begingroup$ Yeah, sorry - overlooked that $\endgroup$ – Maren Apr 25 '13 at 14:59
  • $\begingroup$ This is helpful. $\endgroup$ – Git Gud Apr 25 '13 at 15:07
4
$\begingroup$

You can use

$$9^n-5^n=(9-5)(9^{n-1}+9^{n-2}\cdot 5+..+5^{n-1})$$

This solution has hidden induction in it.

Alternately, by induction:

$$9^{n+1}-5^{n+1}=9^{n+1}-9^{n}\cdot 5+9^{n}5-5^{n+1}=9^n\cdot 4+5(9^n-5^n)$$

use $P(n)$ and done.

$\endgroup$
1
$\begingroup$

$(a^n-b^n)(a+b)=a^{n+1}-b^{n+1}+ab(a^{n-1}-b^{n-1})$

$\implies a^{n+1}-b^{n+1}=(a^n-b^n)(a+b)-ab(a^{n-1}-b^{n-1})$

If $a,b,n$ are positive integers,

if $(a-b)$ divides $(a^n-b^n)$ and $(a^{n-1}-b^{n-1}),$ it will divide $a^{n+1}-b^{n+1}$

Now for $n=0, a^0-b^0=0$ which is divisible by $(a-b)$ for $ab(a-b)\ne0$

for $n=1, a^1-b^1=a-b$

Alternatively, the way N.S. has solved it : $a^{n+1}-b^{n+1}=a^n(a-b)+b(a^n-b^n)$

$\endgroup$
  • $\begingroup$ The latter is a special case of the proof of the Congruence Product Rule - see my answer. $\endgroup$ – Math Gems Apr 25 '13 at 20:15
0
$\begingroup$

$\begin{eqnarray}{\bf Hint}&&\rm m\mid\ \ \color{#C00}{a^k\!-\!b^k}\:\ and\:\ m\mid \color{#0A0}{a-b} \\ \Rightarrow\: &&\rm m\mid (\color{#C00}{a^k\!-b^k})\,a\,+\,b^k(\color{#0A0}{a-b})\, =\: a^{k+1}\!-b^{k+1}\end{eqnarray}$

Note $\ $ The above proof is essentially a special case of that for the Congruence Product Rule. Below are proofs of this product rule proof expressed in both divisibility and congruence form, $ $ using the standard notation: $\rm\ \ a\mid b \ :=\ a\,$ divides $\rm\, b,\ $ and $\rm\ \, a\equiv b\ \ (mod\ m) \iff m\mid a-b$

$\begin{eqnarray} \rm {\bf Lemma}\ \ &\rm m\ \ |&\rm\ \, X\!-\!x\quad\ \& &&\rm\! m\ |\: Y\!-\!y \ \Rightarrow\ m\:|\!\!&&\rm XY - \: xy\\ \\ \rm {\bf Proof}\ \ \ \ \ &\rm m\ \ |&\rm (X\!-\!\color{#c00}x)\:\color{#c00}Y\ \,+ &&\rm\, \color{#c00}x\ (\color{#c00}Y\!-\!y)\ \ \ \ = &&\rm XY - \: xy \\ \\ \rm {\bf Lemma}\ \ & &\rm\ \, X\equiv x\quad\ \ \& &&\rm\quad\ Y\equiv y \ \ \ \ \Rightarrow\ &&\rm XY\equiv xy\\ \\ \rm {\bf Proof}\ \ \ \ \ &0\equiv& \rm (X\!-\!\color{#c00}x)\:\color{#c00}Y\,\ + &&\rm\, \color{#C00}x\ (\color{#c00}Y\!-\!y)\ \ \ \ \equiv &&\rm XY - \: xy \\ \end{eqnarray}$

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