Mathematical Induction

[discretec]

Instructions: Use mathematical induction to prove the truth of each of the following assertions for all n>=1.
Problem: n^3+5n is divisible by 6
This is the work I have and would like to know if I am doing it correctly.
n=1
1^3+5(1)=6
Assume n=k
6 divides k^3+5k
n=k+1
6 divides (k+1)^3+5(k+1)
=(k^3+5k)+(3k^2+3k+6)
Conclusion: 6 divides n^3+5n for all n>=1

Thank you in advance for your help.

 

[Deleted member 4993]

Instructions: Use mathematical induction to prove the truth of each of the following assertions for all n>=1.
Problem: n^3+5n is divisible by 6
This is the work I have and would like to know if I am doing it correctly.
n=1
1^3+5(1)=6
Assume n=k
6 divides k^3+5k
n=k+1
6 divides (k+1)^3+5(k+1)
=(k^3+5k)+(3k^2+3k+6) <<< How do you know that 3k^2 + 3k is divisible by 6? (It is of course - but you need to show it)
Conclusion: 6 divides n^3+5n for all n>=1

Thank you in advance for your help.

 

[discretec]

Would showing it like this be correct?
n=k+1
(k+1)^3+5(k+1)
(k+1)(k+1)
(k^2+k+k+1)(k+1)
k^3+k^2+k^2+k+k^2+k+k+1
k^3+3k^2+3k+1

 

[chrisr]

That's partways.

You can use the 2 step procedure of
(i) test for the first k, usually k = 1.
(ii) then test for k+1.

It helps to be clear on how Induction proves the hypothesis.

How it does so is as follows......

Suppose the hypothesis is true for some n and it "looks true" for a few more n.
If we could prove that being true for n causes it to be true for n+1, then this
links every pair of adjacent terms if we write the hypothesis as a sequence.

This means that if we've proven the above then the chain-reaction is...
true for n=1 causes true for n=2 causes true for n=3 causes true for n=4 causes............

Therefore, what you must prove initially is
true for k causes true for k+1.

Here is how this is done in this case...

(k+1)[sup:z5x1qsnh]3[/sup:z5x1qsnh]=k[sup:z5x1qsnh]3[/sup:z5x1qsnh]+3k[sup:z5x1qsnh]2[/sup:z5x1qsnh]+3k+1
therefore (k+1)[sup:z5x1qsnh]3[/sup:z5x1qsnh]+5(k+1) = k[sup:z5x1qsnh]3[/sup:z5x1qsnh]+5k +(3k[sup:z5x1qsnh]2[/sup:z5x1qsnh]+3k+6)

Now, if (3k[sup:z5x1qsnh]2[/sup:z5x1qsnh]+3k+6) is divisible by 6, then
if k[sup:z5x1qsnh]3[/sup:z5x1qsnh]+5k really is divisible by 6, then (k+1)[sup:z5x1qsnh]3[/sup:z5x1qsnh]+5(k+1) will be too.

The sublety of this is that we haven't proven directly whether or not n[sup:z5x1qsnh]3[/sup:z5x1qsnh]+5n is divisible by 6.
We are first only discovering if we can set up the adjacent term link.
It's like setting a trail of gunpowder, ready to light the fuse,
or stacking up a series of dominoes, ready to topple the first one.

The question now is...
Is 3k[sup:z5x1qsnh]2[/sup:z5x1qsnh]+3k+6 divisible by 6?
Is 6(k[sup:z5x1qsnh]2[/sup:z5x1qsnh]/2 + k/2 +1) divisible by 6? Yes, if k[sup:z5x1qsnh]2[/sup:z5x1qsnh]+k is a multiple of 2.

If k is even, then k[sup:z5x1qsnh]2[/sup:z5x1qsnh]+k is a multiple of 2.
If k is odd then k[sup:z5x1qsnh]2[/sup:z5x1qsnh] is odd, but odd + odd is even.

So we only need find out if now if 1[sup:z5x1qsnh]3[/sup:z5x1qsnh]+5(1) is divisible by 6, which it is.

 

[Random]

Wouldn't this be a lot easier and straightforward to break it into two cases and directly prove it works for even positive integers and odd positive integers? You have to anyway to show k^2+k is divisible by two. Just checking.

 

[daon]

Wouldn't this be a lot easier and straightforward to break it into two cases and directly prove it works for even positive integers and odd positive integers? You have to anyway to show k^2+k is divisible by two. Just checking.

Maybe, but that wasn't what was asked.