The Student Room Group

The 2012 STEP Results Discussion Thread

Scroll to see replies

Original post by ian.slater
Sadly you've been given one of the methods already. If you are given a problem like this, a good way to start is to check that it works for small cases of n. And then you try to look for why it's true. Is there some pattern? Then you try to turn the pattern into a proof.

You are probably already familiar with two kinds of maths problem - those you know how to do and those you don't. There is a third kind - those you can figure out how to do if you work on them for long enough.

There is a more direct method than modular arithmetic.

Right, I believe that I have come up with a proof. But I don't think it is what you expected, as it is quite long winded. I think I have proved it anyway. I have basically proved that the difference in the differences of the rise of the output when n is increased by 1 each time, is always equal to 6. That is quite complicated and difficult to understand.

E.g. When n=4&5, your outputs are 39 and 93. 93-39=54.
When n=3&4, '' '' '' 9 and 39. 39-9=30
Now, 54-30=24.

When you repeat this for the next set of numbers (4&5with5&6), the final number you get is 30, which is exactly 6 more than 26. Then this continually increases by 6 as you increase the values of n like I just did. This is the pattern I found. Then I proved that you will always get that number 6 no matter what with some long winded basic algebra. Considering that n^3 -7n + 3 gives a multiple of 3 for a few tested values of n, and then proving what I have stated that I have proved, does this then prove that the output will always be a multiple of 3 (Because 6 is a multiple of three too)?

I told you it was long winded /:

EDIT: This is the Algebra I did...


(((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n=6\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n} =6

Cancels to...

((n3+3n24n3)(n37n+3))((n37n+3)(n33n24n+9))n=6\frac{\left((n^3 +3n^2 -4n -3) - (n^3 -7n +3)\right) - \left((n^3 -7n +3) - (n^3 -3n^2 -4n +9)\right)}{n} =6

Cancels to...

(3n2+3n6)(3n23n6)n=6\frac{(3n^2 +3n -6) - (3n^2 -3n -6)}{n} =6

Cancels to...

6nn=6\frac{6n}{n} =6

Which basically is

6=6 6=6
(edited 11 years ago)
Reply 1481
I wonder if you could get away with a proof that is almost identical to induction. If you can prove that for n = 1 is true, and then consider what happens between the differences - that is, when you have n^3 - 7n + 3 and (n+1)^3 - 7(n+1) + 3 - is a multiple of three, then n^3 - 7n + 3 must be a multiple of three because you are adding multiple of threes to your first term...it's not strictly induction if you don't put on the extra comments and assuming it's true for n = k, no?
Original post by Blazy
I wonder if you could get away with a proof that is almost identical to induction. If you can prove that for n = 1 is true, and then consider what happens between the differences - that is, when you have n^3 - 7n + 3 and (n+1)^3 - 7(n+1) + 3 - is a multiple of three, then n^3 - 7n + 3 must be a multiple of three because you are adding multiple of threes to your first term...it's not strictly induction if you don't put on the extra comments and assuming it's true for n = k, no?

I have added the algebra that I did onto my last comment... Can you make sense out of it? Or do I need to explain why I did things to make it understandable?
Reply 1483
Original post by CharlieBoardman
Right, I believe that I have come up with a proof. But I don't think it is what you expected, as it is quite long winded. I think I have proved it anyway. I have basically proved that the difference in the differences of the rise of the output when n is increased by 1 each time, is always equal to 6. That is quite complicated and difficult to understand.

E.g. When n=4&5, your outputs are 39 and 93. 93-39=54.
When n=3&4, '' '' '' 9 and 39. 39-9=30
Now, 54-30=24.

When you repeat this for the next set of numbers (4&5with5&6), the final number you get is 30, which is exactly 6 more than 26. Then this continually increases by 6 as you increase the values of n like I just did. This is the pattern I found. Then I proved that you will always get that number 6 no matter what with some long winded basic algebra. Considering that n^3 -7n + 3 gives a multiple of 3 for a few tested values of n, and then proving what I have stated that I have proved, does this then prove that the output will always be a multiple of 3 (Because 6 is a multiple of three too)?

I told you it was long winded /:


You're almost there. Instead of subbing specific values of n into your expression, consider the difference between any two consecutive values of it. ie. ((n+1)37(n+1)+3)(n37n+3)((n+1)^3 - 7(n+1) + 3) - (n^3 - 7n + 3) and see what this is.
(edited 11 years ago)
Original post by Blazy
I wonder if you could get away with a proof that is almost identical to induction. If you can prove that for n = 1 is true, and then consider what happens between the differences - that is, when you have n^3 - 7n + 3 and (n+1)^3 - 7(n+1) + 3 - is a multiple of three, then n^3 - 7n + 3 must be a multiple of three because you are adding multiple of threes to your first term...it's not strictly induction if you don't put on the extra comments and assuming it's true for n = k, no?


You don't need to write down the silly paragraph they make you write for induction proofs at A-level in STEP. You could write something like:
x_(n+1) = x_n + 3y_n where y_n is an integer (*)
As x_0 is divisible by 3, and (*) clearly means if x_n is divisible by 3, so is x_(n+1), x_n is divisible by 3 for all n0n \geq 0 by induction.
(edited 11 years ago)
Original post by Zuzuzu
You're almost there. Instead of subbing specific values of n into your expression, consider the difference between any two consecutive values of it. ie. ((n+1)37(n+1)+3)(n37n+3)((n+1)^3 - 7(n+1) + 3) - (n^3 - 7n + 3) and see what this is.

I was just describing how I found the pattern that's all :smile: I've added my algebra proof onto the original comment a few minutes ago, I think you might have missed it :smile:
Original post by CharlieBoardman
Right, I believe that I have come up with a proof. But I don't think it is what you expected, as it is quite long winded. I think I have proved it anyway. I have basically proved that the difference in the differences of the rise of the output when n is increased by 1 each time, is always equal to 6. That is quite complicated and difficult to understand.

E.g. When n=4&5, your outputs are 39 and 93. 93-39=54.
When n=3&4, '' '' '' 9 and 39. 39-9=30
Now, 54-30=24.

When you repeat this for the next set of numbers (4&5with5&6), the final number you get is 30, which is exactly 6 more than 26. Then this continually increases by 6 as you increase the values of n like I just did. This is the pattern I found. Then I proved that you will always get that number 6 no matter what with some long winded basic algebra. Considering that n^3 -7n + 3 gives a multiple of 3 for a few tested values of n, and then proving what I have stated that I have proved, does this then prove that the output will always be a multiple of 3 (Because 6 is a multiple of three too)?

I told you it was long winded /:

EDIT: This is the Algebra I did...


(((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n=6\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n} =6

Cancels to...

((n3+3n24n3)(n37n+3))((n37n+3)(n33n24n+9))n=6\frac{\left((n^3 +3n^2 -4n -3) - (n^3 -7n +3)\right) - \left((n^3 -7n +3) - (n^3 -3n^2 -4n +9)\right)}{n} =6

Cancels to...

(3n2+3n6)(3n23n6)n=6\frac{(3n^2 +3n -6) - (3n^2 -3n -6)}{n} =6

Cancels to...

6nn=6\frac{6n}{n} =6

Which basically is

6=6 6=6


In this working, you've basically assumed the identity you want is true, then shown you don't get a contradiction - it's better to state what you want to show, then start with one side, and get to the other. e.g. for proving (x+1)^2 + (x-1)^2 = 2x^2 + 2, I'd write:

WTS (x+1)^2 + (x-1)^2 = 2x^2 + 2.
LHS = (x+1)^2 + (x-1)^2 = (x^2 + 2x + 1) + (x^2 -2x +1)
= 2x^2 + 2 = RHS.
Reply 1487
Original post by CharlieBoardman
I have added the algebra that I did onto my last comment... Can you make sense out of it? Or do I need to explain why I did things to make it understandable?


The intended method I think (someone has probably posted this already, I have not checked):

Spoiler

Original post by matt2k8
In this working, you've basically assumed the identity you want is true, then shown you don't get a contradiction - it's better to state what you want to show, then start with one side, and get to the other. e.g. for proving (x+1)^2 + (x-1)^2 = 2x^2 + 2, I'd write:

WTS (x+1)^2 + (x-1)^2 = 2x^2 + 2.
LHS = (x+1)^2 + (x-1)^2 = (x^2 + 2x + 1) + (x^2 -2x +1)
= 2x^2 + 2 = RHS.

But by proving that I didn't get a contradiction, doesn't that mean than the proof is correct that all values of n will get the answer 6? Therefore proving the statement?

Also, I don't know how I would do what you suggested to my equation anyway...
Original post by twig
The intended method I think (someone has probably posted this already, I have not checked):

Spoiler


I can see how you've got the RHS, but I'm not sure as to how that proves it? :frown:
Original post by CharlieBoardman
I can see how you've got the RHS, but I'm not sure as to how that proves it? :frown:


how often do multiples of 3 repeat?
Original post by twig
The intended method I think (someone has probably posted this already, I have not checked):

Spoiler



Original post by ben-smith
how often do multiples of 3 repeat?

Is it because (n-1)(n)(n+1) is divisible by 3..
And that 3(1-2n) is obviously divisible by 3?
Reply 1492
Original post by twig
The intended method I think (someone has probably posted this already, I have not checked):

Spoiler



Yeah I was gonna post a version that works along the lines of taking things and adding things (except mine was a lot worse...)

Spoiler



I guess it's that's what's nice about maths - you can have many different solutions, ugly and beautiful...
Original post by Blazy
Yeah I was gonna post a version that works along the lines of taking things and adding things (except mine was a lot worse...)

Spoiler



I guess it's that's what's nice about maths - you can have many different solutions, ugly and beautiful...


That method is fine but the implication symbols should be equals signs.
Original post by CharlieBoardman
But by proving that I didn't get a contradiction, doesn't that mean than the proof is correct that all values of n will get the answer 6? Therefore proving the statement?

Also, I don't know how I would do what you suggested to my equation anyway...


You'd say:
WTS (((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n=6\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n} =6 .

LHS = (((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n}
=((n3+3n24n3)(n37n+3))((n37n+3)(n33n24n+9))n=\frac{\left((n^3 +3n^2 -4n -3) - (n^3 -7n +3)\right) - \left((n^3 -7n +3) - (n^3 -3n^2 -4n +9)\right)}{n}
=(3n2+3n6)(3n23n6)n= \frac{(3n^2 +3n -6) - (3n^2 -3n -6)}{n}
=6nn=6= \frac{6n}{n} = 6 = RHS.
Original post by matt2k8
You'd say:
WTS (((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n=6\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n} =6 .

LHS = (((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n}
=((n3+3n24n3)(n37n+3))((n37n+3)(n33n24n+9))n=\frac{\left((n^3 +3n^2 -4n -3) - (n^3 -7n +3)\right) - \left((n^3 -7n +3) - (n^3 -3n^2 -4n +9)\right)}{n}
=(3n2+3n6)(3n23n6)n= \frac{(3n^2 +3n -6) - (3n^2 -3n -6)}{n}
=6nn=6= \frac{6n}{n} = 6 = RHS.

Ah, so what I did was correct, I just had to lay it out slightly differently?
Original post by matt2k8
You'd say:
WTS (((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n=6\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n} =6 .

LHS = (((n1)37(n+1)+3)(n37n+3))((n37n+3)((n1)37(n1)+3))n\frac{\left(\left((n-1)^3 -7(n+1) +3\right) - \left(n^3 -7n +3\right)\right) - \left(\left(n^3 -7n +3\right) - \left((n-1)^3 -7(n-1) +3\right)\right)}{n}
=((n3+3n24n3)(n37n+3))((n37n+3)(n33n24n+9))n=\frac{\left((n^3 +3n^2 -4n -3) - (n^3 -7n +3)\right) - \left((n^3 -7n +3) - (n^3 -3n^2 -4n +9)\right)}{n}
=(3n2+3n6)(3n23n6)n= \frac{(3n^2 +3n -6) - (3n^2 -3n -6)}{n}
=6nn=6= \frac{6n}{n} = 6 = RHS.


Wouldn't it be shorter and quicker just using modular arithmetic?
Original post by GreenLantern1
Wouldn't it be shorter and quicker just using modular arithmetic?


Yes, as I said in one of my earlier posts - I was just showing a better way to write out the proof of the identity used in his proof.
Reply 1498
I want to prepare for STEP 1 only...is it worth going through 'Advanced Problems in Core Mathematics' by Stephen Siklos? Or is the focus there primarily on STEP 2 and 3?

Also how is everyone preparing for the applied questions? In particular, the probability ones?
Original post by matt2k8
Yes, as I said in one of my earlier posts - I was just showing a better way to write out the proof of the identity used in his proof.


How would you show a modular arithmetic proof of this problem? I am not quite sure :|

EDIT: And can you use modular arithmetic in STEP, since it isn't on the A Level course?
(edited 11 years ago)

Quick Reply

Latest