Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Hint: can you write $(k+1)^5-(k+1)$ in terms of $k^5-k$? Obviously there will be something left over, but can you prove that is also divisible by 5 another way? –  Michael Grant Apr 4 '13 at 1:15
    
What if I factor out a k? I believe that would give me $k^5 - 5$. –  blutuu Apr 4 '13 at 1:18
    
But you don't know anything about $k^5-5$. Oh well, it looks like someone answered for you! Which is fine, but I was hoping with a little hint you could get it! :-) –  Michael Grant Apr 4 '13 at 1:19
1  
I guess, it wants to go to the exponent, $27\,|\,10^n+18n-1$, and then $10^{k+1}+18k+17$... –  Berci Apr 4 '13 at 1:21

3 Answers 3

up vote 9 down vote accepted

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

share|improve this answer
    
I understand the base case where it states $k^5 - k = 5n$, which holds true. Expanding $(k+1)^5$ shows that it also is a multiple of 5 which is visible by factoring ($k^5 - 5)--a multiple of 5. Am I reading that correctly? –  blutuu Apr 4 '13 at 1:52
    
@blutuu: $k^5-k=5n$ isn’t the base case; the base case is either $5\mid 0^5-0$ or $5\mid 1^5-1$, depending on just how the theorem was stated. $5\mid k^5-k$ is the induction hypothesis. It’s not that $(k+1)^5$ is a multiple of $5$; in general it isn’t. What the calculation shows is that $(k+1)^5-(k+1)$ is a multiple of $5$ if $k^5-k$ is, which is exactly what we need to show for the induction step. –  Brian M. Scott Apr 4 '13 at 1:55
    
That last sentence clears up my confusion. Thanks. –  blutuu Apr 4 '13 at 2:25
    
@blutuu: Oh, good. You’re welcome. –  Brian M. Scott Apr 4 '13 at 2:27

Hint $\ \ n^5\!-\!n = n(n^2\!-\!1)(n^2\!-\!4\! +\! 5) = (n\!-\!2)(n\!-\!1)n(n\!+\!1)(n\!+\!2)+ 5n(n^2\!-\!1)$

Thus it suffices to show that $\,5\,$ divides a product of $\,5\,$ consecutive integers. In fact, any sequence of $\,n\,$ consecutive naturals has an element divisible by $\,n\,$. This has a simple proof by induction: shifting such a sequence by one does not change its set of remainders mod $\,n,\,$ since it effectively replaces the old least element $\:\color{#C00}a\:$ by the new greatest element $\:\color{#C00}{a+n}$

$$\begin{array}{}& \color{#C00}a, &\!\!\!\! a+1, &\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1 & \\ \to & &\!\!\!\! a+1,&\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1, &\!\!\!\! \color{#C00}{a+n} \end{array}\qquad$$

Since $\: \color{#C00}{a\,\equiv\, a\!+\!n}\pmod n,\:$ the shift does not change the remainders in the sequence. Thus the remainders are the same as the base case $\ 0,1,2,\ldots,n-1\ =\: $ all $ $ possible remainders mod $\,n.\,$ Therefore the sequence has an element with remainder $\,0,\,$ i.e. an element divisible by $\,n.$

share|improve this answer

Also note that all the binomial coefficients $C(p, k) = \frac{p!}{k!(p-k)!}$ when $p$ is a prime are divisible by $p$ except for $k=0$ and $k=p$ (since $p$ is in the numerator but not in the denominator).

This is enough to show by induction that $n^p-n$ is divisible by $p$ for all positive integers $n$: True for $n=1$ and, for the induction,

$\begin{align} ((n+1)^p-(n+1))-(n^p-n) &=(n+1)^p-n^p-1\\ &= (n^p+(\text{terms divisible by p})+1)-n^p-1\\ &= (\text{terms divisible by p}) \end{align}$ .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.