# How to conclude proof by induction?

Watch
Announcements
#1
Given n is a positive integer, prove that n(n+1)(2n+1) is divisible by 6.
This is what I did:
f(k)=k(k+1)(2k+1)= 2k^3+9k^2+k
f(k+1)= 2k^3 +9k^2 +13k +6

f(k+1) - f(k)= 6k^2 +12k +6

f(k+1)= f(k) + 6k^2 + 6k + 6.
Then how do I conclude it?
0
12 years ago
#2
dunno if thats right, but concluding statement is QED
0
#3
(Original post by Prokaryotic_crap)
dunno if thats right, but concluding statement is QED
QED?
Well it must be correct, the maths works, it's indisputable that 6k^2 + 12k + 6 is divisible by 6.
0
12 years ago
#4
Um, I don't think that wants to be a proof by induction, unless it specifically said otherwise.

But anyway, you have to first prove that it's true for k = 1. That's how you should start any proof by induction. Then you say:

Spoiler:
Show
Therefore if true for k, true for k + 1.
True for k = 1, therefore true for k = 2, 3, 4,...n.
QED

Or words to that effect.
0
#5
(Original post by Bezzler)
Um, I don't think that wants to be a proof by induction, unless it specifically said otherwise.

But anyway, you have to first prove that it's true for k = 1. That's how you should start any proof by induction. Then you say:

Spoiler:
Show
Therefore if true for k, true for k + 1.
True for k = 1, therefore true for k = 2, 3, 4,...n.
QED

Or words to that effect.
It states use 'proof by induction'.
What is QED?
0
12 years ago
#6
I think for proof by induction, a better concluding statement is "and hence by the principle of mathematical induction P(n) is true for all n in S" Where P(n) is the statement you are proving and S is the set of values for which you've proved P(n) to be true.

Then again, I can't really see what the OP is trying to do here. How does your working relate to the problem?

Additionally, does the problem state you have to use induction? There is a much simpler way to show this result.

EDIT: QED is Quod Erat Demonstrandum, which literally translates from the latin to "which was to be demonstrated".
0
#7
(Original post by DoMakeSayThink)
I think for proof by induction, a better concluding statement is "and hence by the principle of mathematical induction P(n) is true for all n in S" Where P(n) is the statement you are proving and S is the set of values for which you've proved P(n) to be true.

Then again, I can't really see what the OP is trying to do here. How does your working relate to the problem?

Additionally, does the problem state you have to use induction? There is a much simpler way to show this result.
Yes.
Well I've got P(n) in a from which is a lot easier to see that the expression is divisible by 6.
0
12 years ago
#8
(Original post by vinsta)
Yes.
Well I've got P(n) in a from which is a lot easier to see that the expression is divisible by 6.
k(k+1)(k+2) does not equal k(k+1)(2k+1).
0
12 years ago
#9
I don't know how you should go about concluding it; at A-level our teacher was really picky about how the wording we used to finish it (we learnt some ridiculous phrase and wrote it down at the end of every proof), but since then I haven't met anyone who really seems to care. However, you would probably be a lot better writing out the proof far more clearly so markers can see what steps you are doing IE something more like this (not that it's perfect or anything!):

Statement: n(n+1)(2n+1) is divisible by 6 for all natural numbers n >= 1

Base Case: n=1
f(1) = 1 *2 * 3 = 6
which clearly divides 6, so the statement holds for n = 1

Assumption: n=k
Assume that
f(k) = k(k+1)(2k+1) = 2k^3+3k^2+k
is divisible by 6.

Inductive Step: n=k+1
f(k+1) = (k+1)(k+2)(2(k+1)+1)
= 2k^3 +9k^2 +13k +6
= (2k^3+3k^2+k) + (6k^2 +12k +6)
= (2k^3+3k^2+k) + 6 * (k^2 +2k +1)

Since "6 * (k^2 +2k +1)" is clearly divisible by 6, and we assumed that (2k^3+3k^2+k) is then (2k^3+3k^2+k) + 6 * (k^2 +2k +1) must be divisible by 6 too.

[Therefore the statement is valid for all natural numbers n >= 1]
0
#10
(Original post by DoMakeSayThink)
k(k+1)(k+2) does not equal k(k+1)(2k+1).
I've edited my first post.
0
12 years ago
#11
(Original post by vinsta)
I've edited my first post.
Icy_Mikki's post above is a good structure to follow, although I'd still recommend using the concluding statement I mentioned earlier.
0
#12
(Original post by Icy_Mikki)
I don't know how you should go about concluding it; at A-level our teacher was really picky about how the wording we used to finish it (we learnt some ridiculous phrase and wrote it down at the end of every proof), but since then I haven't met anyone who really seems to care. However, you would probably be a lot better writing out the proof far more clearly so markers can see what steps you are doing IE something more like this (not that it's perfect or anything!):

Statement: n(n+1)(2n+1) is divisible by 6 for all natural numbers n >= 1

Base Case: n=1
f(1) = 1 *2 * 3 = 6
which clearly divides 6, so the statement holds for n = 1

Assumption: n=k
Assume that
f(k) = k(k+1)(2k+1) = 2k^3+3k^2+k
is divisible by 6.

Inductive Step: n=k+1
f(k+1) = (k+1)(k+2)(2(k+1)+1)
= 2k^3 +9k^2 +13k +6
= (2k^3+3k^2+k) + (6k^2 +12k +6)
= (2k^3+3k^2+k) + 6 * (k^2 +2k +1)

Since "6 * (k^2 +2k +1)" is clearly divisible by 6, and we assumed that (2k^3+3k^2+k) is then (2k^3+3k^2+k) + 6 * (k^2 +2k +1) must be divisible by 6 too.

[Therefore the statement is valid for all natural numbers n >= 1]
Thanks,
I've shown that the difference between 2 terms is a multiple of 6, that is the same thing as you've done except I simplified mine. See my edited first post, I have done exactly the same thing as you, except I wrote f(k).
0
#13
(Original post by DoMakeSayThink)
Icy_Mikki's post above is a good structure to follow, although I'd still recommend using the concluding statement I mentioned earlier.
Yes, indeed it is, thanks for your concluding statement aswell
0
12 years ago
#14
(Original post by vinsta)
I have done exactly the same thing as you, except I wrote f(k).
Sorry to say this but you haven't! You may have done the same steps but they're meaningless without a good layout and an explanation of what each step is for!
0
12 years ago
#15
As has been said, you need to do the base case, and then say you are doing the induction case. (And actually say that is what you are doing, rather than just doing it without explanation.)

Carrying on from: in the induction case:

Assume is divisible by 6. Then we can write for some .

So . Therefore if is divisible by 6, then so is .

So by induction, is divisible by 6 for all .
0
12 years ago
#16
Therefore proven by Mathematical Induction.
0
#17
(Original post by Icy_Mikki)
Sorry to say this but you haven't! You may have done the same steps but they're meaningless without a good layout and an explanation of what each step is for!
Yes I know, I just wanted to find out how to structure the conclusion, so the explanation etc is irrelevant. Of course I know you have to write an explanation: let n=k n=k+1 etc, but I haven't included it here
0
#18
(Original post by Kolya)
As has been said, you need to do the base case, and then say you are doing the induction case. (And actually say that is what you are doing, rather than just doing it without explanation.)

Carrying on from: in the induction case:

Assume is divisible by 6. Then we can write for some .

So . Therefore if is divisible by 6, then so is .

So by induction, is divisible by 6 for all .
Thanks Kolya, that's definitely cleared up my queries.
0
12 years ago
#19
I suggest:

P(1) is true and, if P(k) is true, then P(k+1) is true. By the principle of induction, P(n) is proved for all positive integers.

In reality, any sensible statement of completion will get the mark for this step.
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### How would you describe the quality of the digital skills you're taught at school?

Excellent (13)
8.18%
Okay (49)
30.82%
A bit lacking (56)
35.22%
Not good at all (41)
25.79%