Thread: A simple proof, just want some checking!

1. A simple proof, just want some checking!

I'm trying to get to grips with mathematical proofs. I think I almost have this, but am missing something.

Q) Prove that if n=m^3-m, where m is an integer, then n is a multiple of 6.

Assume the inverse of the statement, that if n=m^3-m then n is not a multiple of 6.

This implies that n = 6k +{1,2,3,4,5} where k is an integer. In other words, n has a remainder of between 1 and 5 if you try to divide it by 6.

Now I need to show that this implies a contradiction with the original statement (n=m^3-m) for every case, {1,2,3,4,5}.

Case 1: n = 6k+1
By the orignal statement, this is equal to m^3-m. But m^3-m is always even, and 6k+1 is always odd. This is therefore obviously false. The same logic applies to cases 3 and 5.

Case 2: n = 6k+2
Again, by the original statement this is equal to m^3-m. But how do I show that this is false. This time both sides are even?

This is where I get into trouble. I am a bit confused on how to prove that 6k+2=m^3-m leads to an obvious contradiction. I can see that you can disprove it by counter example: If k=1 then n=8, but m^3-m can only take values {0,0,6,24,...}. So in general, the statement is false. In fact, it is only true when the number we add on to 6k is 6, otherwise we always 'miss' the values that m^3-m can take. So I think I can see it in words, but how do I formulate it into a proper proof?

2. Q) Prove that if n=m^3-m, where m is an integer, then n is a multiple of 6.
Base case 1 and 2

$6|(1^3-1) \iff 6|0$

$6|(2^3-2) \iff 6|6$

assume n=k

$6|k^3-k$

Show k+1

$(k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=k^3-k+3k^2+3k=k^3-k+3k(k-1)$

Note that $6|(k^3-k)$ by hypothesis

and $6|[3k(k-1)]$ because either $k$ or $k-1$ is even.

QED

3. thank you, but although I see that you've written a recurrence relation for n, and tried to show that every term is a multiple of 6, does that really qualify as a proof in the strict mathematical sense? I understood that you must always assume the opposite of the given statement, then show this leads to a obviously false statement, such as 0=1. Otherwise you are just deriving implied relationships, not actually proving anything.

4. Originally Posted by Rhetoric
thank you, but although I see that you've written a recurrence relation for n, and tried to show that every term is a multiple of 6, does that really qualify as a proof in the strict mathematical sense? I understood that you must always assume the opposite of the given statement, then show this leads to a obviously false statement, such as 0=1. Otherwise you are just deriving implied relationships, not actually proving anything.
Proof by induction

Show the base case.

Assume n=k

Prove k+1

This shows that the statement is true for ALL integers.

for example

$1+2+3+...n=\frac{n(n-1)}{2}$

This can be shown by induction to be true for all n

5. Proof by contradiction is valid but is by no means the only way to prove something.

6. I see now, thanks.

7. Note that: $n=m^3-m=m\cdot{(m^2-1)}=m\cdot{(m-1)\cdot{(m+1)}}$

That is, the product of 3 consecutive natural numbers. Now, given 2 consecutive numbers one of them must be divisble by 2, and given three consecutive natural numbers one must be divisible by 3. Thus the product is divisble by 6

Or you can remember that $n=m^3-m=m\cdot{(m-1)\cdot{(m+1)}}=6\cdot{\binom{m+1}{3}}$