How to conclude proof by induction?

Watch
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 12 years ago
#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
reply
Prokaryotic_crap
Badges: 18
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report 12 years ago
#2
dunno if thats right, but concluding statement is QED
0
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report Thread starter 12 years ago
#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
reply
Bezzler
Badges: 1
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report 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
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report Thread starter 12 years ago
#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
reply
DoMakeSayThink
Badges: 15
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report 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
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report Thread starter 12 years ago
#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
reply
DoMakeSayThink
Badges: 15
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report 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
reply
Icy_Mikki
Badges: 13
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
Report 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
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report Thread starter 12 years ago
#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
reply
DoMakeSayThink
Badges: 15
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Report 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
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#12
Report Thread starter 12 years ago
#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
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#13
Report Thread starter 12 years ago
#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
reply
Icy_Mikki
Badges: 13
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#14
Report 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
reply
Kolya
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#15
Report 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:f(k+1)= f(k) + 6k^2 + 6k + 6 in the induction case:

Assume f(k) is divisible by 6. Then we can write f(k) = 6m for some m \in \mathbb{Z}.

So f(k+1) = 6(m + k^2 + k + 1). Therefore if f(k) is divisible by 6, then so is f(k+1).

So by induction, f(n) is divisible by 6 for all n \in \mathbb{N}. \square
0
reply
azhao
Badges: 3
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#16
Report 12 years ago
#16
Therefore proven by Mathematical Induction.
0
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#17
Report Thread starter 12 years ago
#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
reply
vinsta
Badges: 12
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#18
Report Thread starter 12 years ago
#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:f(k+1)= f(k) + 6k^2 + 6k + 6 in the induction case:

Assume f(k) is divisible by 6. Then we can write f(k) = 6m for some m \in \mathbb{Z}.

So f(k+1) = 6(m + k^2 + k + 1). Therefore if f(k) is divisible by 6, then so is f(k+1).

So by induction, f(n) is divisible by 6 for all n \in \mathbb{N}. \square
Thanks Kolya, that's definitely cleared up my queries.
0
reply
Mr M
Badges: 20
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#19
Report 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise