# Thread: Divisibility Proofs

1. ## Divisibility Proofs

Having a bit of trouble with this one. Can anyone help?

Many thanks.

Q. $\displaystyle n^3-n$ is divisible by 3 for $\displaystyle n \in \mathbb{N}_o$

Attempt: Step 1: For n = 1...(or P1)
13 - 1 = 0, which can be divided by 3.

Step 2: For n = k...
Assume k3 - k can be divided by 3,
i.e. k3 - k = 3Z, where Z is an integer...1
Show that n = k + 1 is true...(i.e. show that P(k + 1) is true),
i.e. (k + 1)3 - (k + 1) can be divided by 3.
(k + 1)3 - (k + 1) = (k + 1)(k2 - k + 1) - (k + 1) = ...?

2. ## Re: Divisibility Proofs

Nice work so far. Try factoring (k+1) out and using your inductive assumption. I think you should be able to get it from there; let me know if this helps. Good luck!

3. ## Re: Divisibility Proofs

an alternative:

n3 - n = n(n2 - 1) = (n - 1)(n)(n + 1).

these are 3 successive integers, surely one of them is divisible by 3.

(EDIT)

your inductive proof is already on the "wrong track".

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

= (k + 1)(k2 + 2k + 1) - (k + 1) ← you have expanded (k + 1)2 incorrectly.

even so this only leads to an expression involving a quadratic in k, and is not very helpful.

the thing to do is expand (k + 1)3 fully, so we get:

(k + 1)3 - (k + 1) = k3 + 3k2 + 3k + 1 - k - 1

= k3 - k + 3(k2 + k)

= 3z + 3(k2 + k) ← induction hypothesis used HERE

= 3(z + k2 + k), which is clearly a multiple of 3.

4. ## Re: Divisibility Proofs

Originally Posted by GrigOrig99
Step 2: For n = k...
Assume k3 - k can be divided by 3,
i.e. k3 - k = 3Z, where Z is an integer...1
Show that n = k + 1 is true...(i.e. show that P(k + 1) is true)
n = k + 1 is definitely false because above you let n = k. And the fact that n = k + 1 is not the same as P(k + 1) being true. Also, what is P? It's undefined so far.

Originally Posted by GrigOrig99
(k + 1)3 - (k + 1) = (k + 1)(k2 - k + 1) - (k + 1) = ...?
(k + 1)3 - (k + 1) ≠ (k + 1)(k2 - k + 1) - (k + 1).

I recommend fully expanding (k + 1)3 - (k + 1).

5. ## Re: Divisibility Proofs

Ok, continuing on from where I left off:

k3 - k = 3Z $\displaystyle \rightarrow$ k(k2 - 1) = 3Z $\displaystyle \rightarrow$ k(k + 1)(k - 1) = 3Z $\displaystyle \rightarrow$ (k + 1)(k2 - k) = 3Z...1

(k + 1)[(k2 - k + 1) - 1]
(k + 1)[(k2 - k + 1) - 1]
(k + 1)[k2 - k]
From 1...(k + 1)[k2 - k] = 3Z

Is this correct?

6. ## Re: Divisibility Proofs

I'll take a look at the 2 additional posts, as well. I was working on the updated attempt while you guys, Dev. & Emak, were posting your responses .!

7. ## Re: Divisibility Proofs

Originally Posted by GrigOrig99
(k + 1)[(k2 - k + 1) - 1]
(k + 1)[(k2 - k + 1) - 1]
(k + 1)[k2 - k]
From 1...(k + 1)[k2 - k] = 3Z
What does it have to do with (k + 1)3 - (k + 1) being divisible by 3?

8. ## Re: Divisibility Proofs

the whole idea of an inductive proof is to show that P(k+1) follows from P(k).

in this particular instance P(k) is:

k3 - k = 3*"some integer"

so P(k+1) is:

(k+1)3 - (k+1) = 3*"some integer"

note that we don't require the "some integer" to be the same, or for there even to be some relationship between the 2. they just have to be integers.

the strategy is to manipulate P(k+1) so that it becomes:

P(k) and "something else we know is true".

in this case, that means finding a way to express (k+1)3 - (k+1) in terms of k3 - k and "something else". hopefully, that "something else" will be divisible by 3,

so that P(k) and "something else that is divisible by 3" together will give us P(k+1).

so look at the expression (k+1)3 - (k+1). we can obviously get a -k from the -(k+1) part, and the -1 "left over" will go to the "something else". but where are we going to get a k3? from expanding (k+1)3.

when we expand (k+1)3, we get k3+3k2+3k+1. we take the k3 to go with the -k, so that NOW we have the k3-k we can apply P(k) to. this means that the 32+3k+1 goes to the "something else".

so now we've "split" (k+1)3 - (k+1) into two parts:

k3-k (used for our induction hypothesis)
3k2+3k+1 - 1 (our "something else").

note that the 1's cancel in our something else, and the rest of it has a 3 in front. so "something else" is divisible by 3. and that's exactly what we need.

9. ## Re: Divisibility Proofs

Ok, thanks guys.

Also, I'm including an image on an example question from the text book I'm using, as I was wondering if the method of answering divisibility proofs there is a bit different from the way you guys do it. n = k appears to be replacing P(k), n = k + 1 replacing P(k + 1) & so on.

10. ## Re: Divisibility Proofs

I think the method is the same. Note that the proof says, "we must show that the statement is true for n = k + 1" and not "we must show n = k + 1 is true." We could denote the fact that the statement in question holds for n by P(n). Deveno did this in post #8. Then the induction step amounts to assuming P(k) for some k and proving P(k + 1).

11. ## Re: Divisibility Proofs

Ok. Thanks for taking a look at that for me.

12. ## Re: Divisibility Proofs

Deveno's solution is the simplest. Out of the numbers n-1, n, n+1, exactly one of them will be divisible by 3.