Register to reply 
Prove (n^5  n) is divisible by 5 by induction 
Share this thread: 
#1
Jul2008, 02:22 PM

P: 1

here's what Ive done so far...
P(n) = n^5  n n(n1)(n^3+n+1) when n = 5 5 * 4* 131 = 620 620 is a factor of 5. therefore true for n=5 assume true n=k P(k) = k^5  k when n = k+1 P(k+1) = (k+1)(k+11)((k+1)^3 + k+2) = (k+1)(k)(k^3 + 3k^2 + 3k + 1 + k + 2) = (k+1)(k)(k^3 + 3k^2 + 4k + 3) = (k^2+k)(k^3 + 3k^2 + 4k + 3) = k^5 + 4k^4 + 7k^3 + 7k^2 + 3k what shall I do from there? thanks xxx 


#2
Jul2008, 03:21 PM

Sci Advisor
P: 6,076

(n+1)^5=n^5+5n^4+10n^3+10n^2+5n+1
Therefore (n+1)^5(n+1)=n^5n+K, where K is divisible by 5. 


#3
Jul2108, 01:48 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,557

Fizza, why do you start with n= 5 as base case? The statement is also true for n= 1, 2, 3, and 4.
Also you did not use the fact that you are assuming k^{5} k is a multiple of 5. Follow mathman's suggestion. 


#4
Jul2108, 03:09 AM

P: 688

Prove (n^5  n) is divisible by 5 by induction
I'm trying to figure out how the problem was built in the first place.
I'd imagine a similar statement is true for any prime power, since the 'prime rows' of the Pascal triangle are divisible by that prime (except for the ending 1's). 


#5
Jul2108, 08:13 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,557

So you are asking, "Is it true that n^{p} n is divisible by p for p any prime?"
Yes, it is and for exactly the reason you state: if p is prime then [itex]\left(\begin{array}{c}p \\ i\end{array}\right)[/itex] for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition: [tex]\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(pi)!}[/tex] as long as i is neither 0 nor p, 0<pi< p and so neither i! nor (p i)! have a factor of p. Since p! does, the binomial coefficient is divisible by p. (We need p to be prime so that other factors in i! and (p i)! do not "combine" to cancel p.) Now, to show that n^{p} n is divisible by p, do exactly what mathman suggested. First, when n= 1, 1^{p} 1= 0 which is divisible by p. Now assume the statement is true for some k: k^{p} k= mp for some integer m. Then, by the binomial theorem, [tex](k+1)^p= \sum_{i=0}^p \left(\begin{array}{c}p \\ i\end{array}\right) k^i[/itex] subtracting k+1 from that does two things: first it cancels the i=0 term which is 1. Also we can combine the "k" with the i= p term which is k^{p} so we have k^{p} k= mp. The other terms, all with 0< i< p, contain, as above, factors of p. 


#6
Aug1608, 01:50 PM

P: 4

What would be the converse of this ^^^? Could you use "the assuming the opposite" method to prove whether or not this holds?
cheers 


#7
Aug1608, 06:27 PM

HW Helper
P: 5,341

Secondly and more importantly I don't think the factors of n^5  n are simplified enough. I would note that: n^5  n = n(n^41) = n*(n^21)*(n^2+1) = (n1)*n*(n+1)*(n^2+1) Perhaps you can exploit the fact that for any n you necessarily have the number above and below that number that must be a factor of the result? 


Register to reply 
Related Discussions  
Infinitely divisible vs finitely divisible time  General Physics  8  
Prove that phi(a^n  1) is divisible by n  Linear & Abstract Algebra  7  
Prove a^2 + b^2 = 3(s^2 + t^2) implies both a and b must are divisible by 3  Linear & Abstract Algebra  13  
Prove by induction?  Set Theory, Logic, Probability, Statistics  1  
Prove that n^5  5n^3 + 4n is divisible by 120:  General Math  5 