Saturday, November 14, 2015

discrete mathematics - prove by induction that $(a^n - b^n)$ is a multiple of $(a - b)$ for $n geq 1$





Okay so I just finished a final in discrete mathematics and I could not figure out how to finish this proof:



"Prove by mathematical induction, that $(a^n - b^n)$ is a multiple of $(a - b)$ when $a$ and $b$ are integers and $n \geq 1$.



$\underline{Base case: n = 1}$




$(a^1 - b^1) = (a - b)x$



$x = 1$



$a - b = a - b$



$\underline{Inductive Hypothesis:}$



$n = k$ for some $k$




$(a^k - b^k) = (a - b)x$



$\underline{Inductive Step:}$



$n = k + 1$



$(a^{k + 1} - b^{k + 1}) = (a - b)x_1$



$(a \cdot a^{k}) - (b \cdot b^{k}) = (a - b) x_1$




$a \cdot [(a - b)x + b^k] + b \cdot [(a - b)x - a^k]= (a-b)x_1$



$(a -b)xa + ab^k + (a - b)xb - ba^k = (a - b)x_1$



$(a -b)xa + (a - b)xb - ab^k + ba^k = (a - b)x_1$



$(a -b)xa + (a - b)xb + ba^k - ab^k = (a - b)x_1$



.....




I don't know if I did it right but I couldn't get any further than this.


Answer



Assumed $a^k-b^k=(a-b)m,m\in\Bbb Z\implies a^k=b^k+(a-b)m$



We have $a^{k+1}-b^{k+1}=a\times a^k-b^{k+1}=a[b^k+(a-b)m]-b^{k+1}\\=am(a-b)+ab^k-b^{k+1}\\=am(a-b)+b^k(a-b)\\=(am+b^k)(a-b)$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...