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!
Having a bit of trouble with this one. Can anyone help?
Q. is divisible by 3 for
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) = ...?
n3 - n = n(n2 - 1) = (n - 1)(n)(n + 1).
these are 3 successive integers, surely one of them is divisible by 3.
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.
I recommend fully expanding (k + 1)3 - (k + 1).
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.
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.
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).