Divisibility Proof By Induction - Viable Alternative Method

Watch
Surfer Rosa
Badges: 10
Rep:
?
#1
Report Thread starter 3 weeks ago
#1
The specific questions is

Prove by induction that n^3-7n+9 is divisible by 3 for all positive integer n

My approach, which afaict differs from the textbook, is something like

n=1 gives 3=3

Assume that k^3-7k+9 = 3a for some positive integer a

then show that this implies (k+1)^3-7(k+1)+9 = 3b for some positive integer b

(In this case b turns out to be a + k^2 + k - 2)

This seems to fit the description for induction but is different from the approach I've seen in textbooks which I find hard to follow.

Would this general approach be allowed in the exam.
0
reply
mqb2766
Badges: 18
Rep:
?
#2
Report 3 weeks ago
#2
(Original post by Surfer Rosa)
The specific questions is

Prove by induction that n^3-7n+9 is divisible by 3 for all positive integer n

My approach, which afaict differs from the textbook, is something like

n=1 gives 3=3

Assume that k^3-7k+9 = 3a for some positive integer a

then show that this implies (k+1)^3-7(k+1)+9 = 3b for some positive integer b

(In this case b turns out to be a + k^2 + k - 2)

This seems to fit the description for induction but is different from the approach I've seen in textbooks which I find hard to follow.

Would this general approach be allowed in the exam.
Probably, but upload what you've done pls?
Last edited by mqb2766; 3 weeks ago
0
reply
Surfer Rosa
Badges: 10
Rep:
?
#3
Report Thread starter 3 weeks ago
#3
(Original post by mqb2766)
Probably, but upload what you've done pls?
Thanks. I've asked a maths lecturer I know and they say it's fine - which is handy as I find this approach much more straightforward.
0
reply
DFranklin
Badges: 18
Rep:
?
#4
Report 3 weeks ago
#4
(Original post by Surfer Rosa)
Thanks. I've asked a maths lecturer I know and they say it's fine - which is handy as I find this approach much more straightforward.
Did you actually show them what you've done (and what your textbook has done)?

Our scepticism is not about whether "showing k^3-7k+9 = 3a implies (k+1)^3-7(k+1)+9 can be written as 3b..." is a valid method, it's more that it's almost impossible for a proof by induction to NOT do this. So either you are confused or your textbook is.
0
reply
Surfer Rosa
Badges: 10
Rep:
?
#5
Report Thread starter 3 weeks ago
#5
(Original post by DFranklin)
Did you actually show them what you've done (and what your textbook has done)?

Our scepticism is not about whether "showing k^3-7k+9 = 3a implies (k+1)^3-7(k+1)+9 can be written as 3b..." is a valid method, it's more that it's almost impossible for a proof by induction to NOT do this. So either you are confused or your textbook is.
I get the scepticism :-)

Yes. I showed them my method.

I'm sure it amounts to the same thing as the textbook, it's just I find this particular path much easier to follow.

Thinking about it, the key step for me is articulating Proofs by Induction as Show That questions, which gives me something to aim for.

The book approach seemed to me more like ploughing through the algebra and the k+1 form sort of magically appearing at the end.
0
reply
DFranklin
Badges: 18
Rep:
?
#6
Report 3 weeks ago
#6
(Original post by Surfer Rosa)
Yes. I showed them my method.
Fair enough. One thing to be aware of (although this is based on my A-levels and it might be different now):

When I did A-level there was a lot of "boilerplate" expected for a proof by induction, with every proof looking something like:

Let P(n) be the statement "blah blah blah", and then you'd show P(1) was true, and if P(n) was true for n = k, then it was true for n = k+1, and then you'd say "by the principle of mathematical induction, P(n) is true for all n".

At degree level you pretty much *never* do this. e.g. to show n^3 - n is divisible by 3 for all n, a proof might look like:

Proof by induction: True when n = 1, if true for n, then (n+1)^3 -(n+1) = (n^3 - n) + 3n^2+3n + 1 - 1, which is divisible by 3 by IH (induction hypothesis). So true for all n by induction.

This is a (somewhat rare) situation where something that would be fine in a degree might not get the marks at A-level.

Again, just something to be aware of.
Last edited by DFranklin; 3 weeks ago
0
reply
Surfer Rosa
Badges: 10
Rep:
?
#7
Report Thread starter 3 weeks ago
#7
(Original post by DFranklin)
Fair enough. One thing to be aware of (although this is based on my A-levels and it might be different now):

When I did A-level there was a lot of "boilerplate" expected for a proof by induction, with every proof looking something like:

Let P(n) be the statement "blah blah blah", and then you'd show P(1) was true, and if P(n) was true for n = k, then it was true for n = k+1, and then you'd say "by the principle of mathematical induction, P(n) is true for all n".

At degree level you pretty much *never* do this. e.g. to show n^3 - n is divisible by 3 for all n, a proof might look like:

Proof by induction: True when n = 1, if true for n, then (n+1)^3 -(n+1) = (n^3 - n) + 3n^2+3n + 1 - 1, which is divisible by 3 by IH (induction hypothesis). So true for all n by induction.

This is a (somewhat rare) situation where something that would be fine in a degree might not get the marks at A-level.

Again, just something to be aware of.
Thanks. I agree with all of that.
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

Current uni students - are you thinking of dropping out of university?

Yes, I'm seriously considering dropping out (44)
15.66%
I'm not sure (8)
2.85%
No, I'm going to stick it out for now (100)
35.59%
I have already dropped out (4)
1.42%
I'm not a current university student (125)
44.48%

Watched Threads

View All