Hard Induction? (1 Viewer)

[dawso]

hey all, i got this question out of ....some textbook

a) Prove that n^5 - n is divisible by 30 for all positive integers n
b) Prove by induction that 6^n < n! for all integers n > some nO, and find the least value of nO

by trial and error i got nO as 7 (part (B))
for part a, i tried it by induction after putting in my assumption i just had a big long annoying polynomial, it doesnt say induction so maybe its not, but it looks like one, anyone got any ideas, thanks in advance
-dawso

 

[ngai]

b) Prove by induction that 6^n < n! for all integers n > some nO, and find the least value of nO
by trial and error i got nO as 7 (part (B))

u mean 6^8 < 8! ?
1679616 < 40320 ?

try nO = 13

 

[Veck]

I've got an answer for your first one

n0 = 2, so it isn't all positive integers

assume true for n = k

k^5 - k = 30I (where I is some integer)

= k(k^4 - 1)
= k (k^2 - 1)(k^2 +1)
= k(k-1)(k+1)(k^2+1) = 30I

now for n = k+1

= (k+1)(k)(k+2)((k+2)^2 + 1) [from expanded form]

but from before we see that if

k(k-1)(k+1)(k^2+1) = 30I

then k(k+1) = 30I / ((k-1)(k^2 + 1))

so (k+1)(k)(k+2)((k+2)^2 + 1) = 30I(k+2)((k+1)^2 +1) / ((k-1)(k^2 + 1))

which is most certainly divisible by 30

and there we go

*takes a bow*

 

[gordo]

assumption:

n=k

k^5 - k = 30Q
k(k^4 - 1) = 30Q
k(k^2 - 1)(k^2 + 1) = 30Q
k(k - 1)(k + 1)(k^2 + 1) = 30Q
(k + 1) = 30Q / k(k - 1)(k^2 + 1)


for n = k+1

(k + 1)^5 - (k+1)
=(k + 1)[(k + 1)^4 - 1]
=30Q [((k + 1)^4 -1) / (k(k - 1)(k^2 + 1))]

therefore true for n=k+1

 

[Veck]

assumption:

n=k

k^5 - k = 30Q
k(k^4 - 1) = 30Q
k(k^2 - 1)(k^2 + 1) = 30Q
k(k - 1)(k + 1)(k^2 + 1) = 30Q
(k + 1) = 30Q / k(k - 1)(k^2 + 1)


for n = k+1

(k + 1)^5 - (k+1)
=(k + 1)[(k + 1)^4 - 1]
=30Q [((k + 1)^4 -1) / (k(k - 1)(k^2 + 1))]

therefore true for n=k+1

I maintain that my one's better

 

[gordo]

haha,
no subjective bias there now ey

 

[Constip8edSkunk]

does a) specify induction, cuz u can prove it w/out using it

n^5 - n = n(n-1)(n+1)(n^2 - 1)
3 of the factors are consecutive so it is clealy divisible by 3 and 2
if n/5 gives a remainder of 1 then n-1 is divisible by 5
if n/5 gives a remainder of 2 or 3 then n^2-1 is divisble by 5
if the remainder is 4, then n+1 is divisible by 5
only remaining case is if n is divisible by 5... so 5 must also be a factor
it follows that 2*3*5 = 30 is a factor, so it is divisble by 30

b) 6^k < k!
6^(k+1) =6*6^k <6*k! < (k+1)! [as k+1 >6]

 

[dawso]

yeah skunk, thats the type of solution i was lookin 4, gud stuff

 

[dawso]

both gordo and veck's solutions are bummed, u got 30Q outside of a fraction shich isnt nessecarily an integer which means it aint divisible by 30...
eg- if ya put k=3 in2 either one, u get a fraction for both which stuffs up the whole solution, anyone got any other ideas??

 

[gordo]

the fraction simplifies to an integer equation with pronumerals

 

[BillyMak]

Then you would have to show that for your answer to be right.

 

[Archman]

don't bother guys, a) is not an induction questions. those fractions dun work out. you more or less hafta follow skunk's way, (even if u try to take the induction paths). Think about it you are all trying to prove that n^5-n divides (n+1)^5-(n+1) which is not true.

 

[gordo]

i'll admit defeat

 

[mr EaZy]

in the real HSC if its an induction quest, it will say so. OR else, i would look up how many marks its worth