# Divisibility Proof By Induction - Viable Alternative Method

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

The specific questions is

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

n=1 gives 3=3

Assume that

then show that this implies

(In this case

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.

**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 athen 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

Report

#2

(Original post by

The specific questions is

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

n=1 gives 3=3

Assume that

then show that this implies

(In this case

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.

**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 athen 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.

Last edited by mqb2766; 3 weeks ago

0

reply

(Original post by

Probably, but upload what you've done pls?

**mqb2766**)Probably, but upload what you've done pls?

0

reply

Report

#4

(Original post by

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.

**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.

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

(Original post by

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.

**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.

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

Report

#6

(Original post by

Yes. I showed them my method.

**Surfer Rosa**)Yes. I showed them my method.

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

(Original post by

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.

**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.

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top