Sunday, May 27, 2018

discrete mathematics - Prove $(n^5-n)$ is divisible by 5 by induction.



So I started with a base case $n = 1$. This yields $5|0$, which is true since zero is divisible by any non zero number. I let $n = k >= 1$ and let $5|A = (k^5-k)$. Now I want to show $5|B = [(k+1)^5-(k+1)]$ is true....




After that I get lost.



I was given a supplement that provides a similar example, but that confuses me as well.



Here it is if anyone wants to take a look at it:



Prove that for all n elements of N, $27|(10n + 18n - 1)$.



Proof:
We use the method of mathematical induction. For $n = 1$, $10^1+18*1-1 = 27$.

Since $27|27$, the statement is correct in this case.



Let $n = k = 1$ and let $27|A = 10k + 18k - 1$.



We wish to show that $27|B = 10k+1 + 18(k + 1) - 1 = 10k+1 + 18k + 17$.



Consider $C = B - 10A$ ***I don't understand why A is multiplied by 10.
$= (10k+1 + 18k + 17) - (10k+1 + 180k - 10)$



$= -162k + 27

= 27(-6k + 1)$.



Then $27|C$, and $B = 10A+C$. Since $27|A$ (inductive hypothesis) and $27|C$, then
$B$ is the sum of two addends each divisible by $27$. By Theorem 1 (iii), $27|B$, and
the proof is complete.


Answer



Your induction hypothesis is that $5\mid k^5-k$, which means that $k^5-k=5n$ for some integer $n$. Now



$$\begin{align*}
(k+1)^5-(k+1)&=\left(k^5+5k^4+10k^3+10k^2+5k+1\right)-(k+1)\\

&=k^5+5k^4+10k^3+10k^2+5k-k\\
&=(k^5-k)+5k^4+10k^3+10k^2+5k
\end{align*}$$



can you see why that must be a multiple of $5$?


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