Hey there! Sign in to join this conversationNew here? Join for free
 You are Here: Home >< Maths

Mathematical Proof Problem! Oxbridge interview, Watch

1. This is something you are asked to prove from a set of sample questions for a mathematics interview at Downing.

Does anybody know how to prove the above formula? I have seen a couple of methods using g(n+1) -g(n) = g(n), meaning g(n+1)=2g(n). But I'm not too sure if this is a normal method of proof, or if the writer just noticed that g(n+1)-g(n)=g(n), after several trials of trying to prove this? Or simply because 2^n + 2^n =2^(n+1), hence the above equation must hold?

Furthermore, does anyone know a way to prove this by induction? Any method is proof is fine, though.

Finally, for any teachers/graduates, does the fact that

and setting a=b=1, prove this?
2. (Original post by DomStaff)
This is something you are asked to prove from a set of sample questions for a mathematics interview at Downing.

Does anybody know how to prove the above formula? I have seen a couple of methods using g(n+1) -g(n) = g(n), meaning g(n+1)=2g(n). But I'm not too sure if this is a normal method of proof, or if the writer just noticed that g(n+1)-g(n)=g(n), after several trials of trying to prove this? Or simply because 2^n + 2^n =2^(n+1), hence the above equation must hold?

Furthermore, does anyone know a way to prove this by induction? Any method is proof is fine, though.

Finally, for any teachers/graduates, does the fact that

and setting a=b=1, prove this?
Why is that last one for teachers/graduates only? :P Yes, that final formula proves it, but why is that formula true?

The easiest way to see it is: is the number of subsets of of size . Hence the sum is just the number of subsets of . What is that number?

ETA: You could also do an induction using Pascal's triangle, if you can assume the recurrence relation form of Pascal's triangle.
3. (Original post by Smaug123)
The easiest way to see it is: is the number of subsets of of size . Hence the sum is just the number of subsets of . What is that number?
Whatever "that number" is (and it's indeed the correct one), then you'd need to prove it has that value, so I think that you're just begging the question here.
4. (Original post by atsruser)
Whatever "that number" is (and it's indeed the correct one), then you'd need to prove it has that value, so I think that you're just begging the question here.
Yes, that was the point of the question - I wasn't giving a solution, but a hint. It's much easier to prove the equivalent statement that the number of subsets is 2^n than to prove the original statement, unless you're allowed to use both that Pascal's triangle is generated by the recurrence relation, and also that it has the binomial coefficients as its entries.
5. (Original post by Smaug123)
Why is that last one for teachers/graduates only? :P Yes, that final formula proves it, but why is that formula true?

The easiest way to see it is: is the number of subsets of of size . Hence the sum is just the number of subsets of . What is that number?

ETA: You could also do an induction using Pascal's triangle, if you can assume the recurrence relation form of Pascal's triangle.
I apologise for my lack of knowledge here, I have only just finished year 12 (almost), so I expected to have all the 'required' knowledge to tackle Oxbridge problems of this kind; apparently I was wrong.

EDIT:
Just a thought, a guess, perhaps.
no. of subsets {1,2,3...n} of size r, so let n=3 r=2. We have {1,2}, {2,3} and {1,3}, so 3 overall. Likewise n=4 r=2=3, {1,2,3} {1,2,4} {2,3,4} {1,3,4}. And so on...
Is this what you meant by the number of subsets of size r?
6. 3 ways of doing this.

You could do it by induction.

You could use the formula for the binomial expansion of (1+1)^n.

You could consider the total number of subsets of {1,2,...,n}.

If you want me to clarify any of these just ask, I haven't given decent answers as it's best to work through it yourself.
7. (Original post by atsruser)
Whatever "that number" is (and it's indeed the correct one), then you'd need to prove it has that value, so I think that you're just begging the question here.
(Original post by Smaug123)
Yes, that was the point of the question - I wasn't giving a solution, but a hint. It's much easier to prove the equivalent statement that the number of subsets is 2^n than to prove the original statement, unless you're allowed to use both that Pascal's triangle is generated by the recurrence relation, and also that it has the binomial coefficients as its entries.
Yes, I see now what you were getting at. But how can you prove that the sum of these is equal to 2^n, that is my problem. I can tell I am lacking expertise in a certain area of mathematics, so if you could point me in the right direction as to how to prove that, that would be great. If I still can't do it, I will get back to you.
8. (Original post by james22)
3 ways of doing this.

You could do it by induction.

You could use the formula for the binomial expansion of (1+1)^n.

You could consider the total number of subsets of {1,2,...,n}.

If you want me to clarify any of these just ask, I haven't given decent answers as it's best to work through it yourself.
By induction, would you consider the method that 2^(n+1) = 2^n + 2^n and then simplify these (in terms of their sums etc.).
9. (Original post by DomStaff)
By induction, would you consider the method that 2^(n+1) = 2^n + 2^n and then simplify these (in terms of their sums etc.).
No, although that may work. I would start with the sum on the LHS, and manipulate it using the induction hypothesis.

EDIT: The induction method is more difficult than I first realised. It will still work, but you should go for the other methods instead.
10. (Original post by DomStaff)
Yes, I see now what you were getting at. But how can you prove that the sum of these is equal to 2^n, that is my problem. I can tell I am lacking expertise in a certain area of mathematics, so if you could point me in the right direction as to how to prove that, that would be great. If I still can't do it, I will get back to you.
First, do you see why it is enough to show that the number of subsets of is ?
11. This was the first part of a step l question. The way they guided you to do it was too consider the expansion of (1+x)^n and let x=1

Posted from TSR Mobile
12. (Original post by Gome44)
This was the first part of a step l question. The way they guided you to do it was too consider the expansion of (1+x)^n and let x=1

Posted from TSR Mobile
Is there something you forgot to put in, because im failing to see a question being asked here?

EDIT: MB, didn't see that this was the first post of page 2 and not OP.

Posted from TSR Mobile
13. (Original post by Jammy Duel)
Is there something you forgot to put in, because im failing to see a question being asked here?

Posted from TSR Mobile
I think he was just pointing out that in the comparable situation of a Cambridge entrance exam (albeit STEP I, which Cambridge don't tend to use for offers) the candidates were steered towards considering the binomial expansion.

Personally I think there's a bit of "over-thinking" going on in this thread. If you've been taught the binomial formula for integral n as part of A level, then setting a = b = 1 to prove the required relation is a perfectly acceptable thing to do!
14. (Original post by Smaug123)
First, do you see why it is enough to show that the number of subsets of is ?
Yes that makes perfect sense. It's just why the number of subsets = 2^n.

The induction proof makes perfect sense, namely that assume k elements {1,2...k} has 2^k subsets, so if we introduce another element, giving us k+1 elements, we have all the subsets from before and each subset with the k+1th element as well, hence 2 * 2^k = 2^k+1.

The proof which I am struggling to get my head around is that for every element we can either put it in the subset or not, hence 2^n different ways of choosing subsets.

But the way it is worded is that x_1 can either be in the subset or not, but all elements end up in a subset, hence I don't see where this comes from? As if we applied this rule to every subset we make, then it seems to me the total would be greater than 2^n; I am obviously overlooking a small, trivial detail.

Edit: I get this now I think, I need to think of the system as a whole. I was thinking of each subset separately, which is obviously wrong.
15. (Original post by davros)
I think he was just pointing out that in the comparable situation of a Cambridge entrance exam (albeit STEP I, which Cambridge don't tend to use for offers) the candidates were steered towards considering the binomial expansion.

Personally I think there's a bit of "over-thinking" going on in this thread. If you've been taught the binomial formula for integral n as part of A level, then setting a = b = 1 to prove the required relation is a perfectly acceptable thing to do!
Yeah I get that but because I want to apply to Cambridge (and don't want to be caught out at interview), I just feel like I should understand every form of the proof of this, as I hate not getting things.
16. (Original post by DomStaff)
Yeah I get that but because I want to apply to Cambridge (and don't want to be caught out at interview), I just feel like I should understand every form of the proof of this, as I hate not getting things.
You won't necessarily be penalised for getting something wrong, your more likely to be penalised for getting something wrong a second time, after the error has been pointed out to you, such as if there is a small subtlety missing out which makes the argument much more complete (could post an example of this sort of thing later)

Posted from TSR Mobile
17. (Original post by Jammy Duel)
You won't necessarily be penalised for getting something wrong, your more likely to be penalised for getting something wrong a second time, after the error has been pointed out to you, such as if there is a small subtlety missing out which makes the argument much more complete (could post an example of this sort of thing later)

Posted from TSR Mobile
Yes would you please post an example?
18. (Original post by DomStaff)
Yes would you please post an example?
I'll use spoilers to let you consider the question before looking at the solution. You should also get given some guidance with questions, after all, they don't expect you to know everything already, they want you to have to think.

So, in a practice interview I was asked something along the lines of "How many trailing, non-decimal, zeros are there are on 100!?"

Spoiler:
Show
With a bit of thinking, and some logic which was along the right lines but incorrect (mainly from not solving it generally enough) I gave an incorrect answer, and was prompted to consider where the trailing zeros come from. Of course, 10=2x5 so to get a trailing zero you require 2x5 of some form in there, there are more 2s than 5s so you can disregard those and just look at the multiples of 5.

So, there are 20 multiples of 5 between 1 and 100 inclusive, so there are 20 trailng zeroes there, 4 of these are also multiples of 25, so there are another 4 trailing zeroes from that, so the answer is 24. Upon giving this justified answer I was told it's correct, however I should, strictly, conclude this explanation by saying that there are no values in the range that are multiples of 125 (being 3​).

After going through this it was followed up by "How many trailing, non-decimal, zeroes in 1000! ?"

Spoiler:
Show
So, this is easy enough to solve, given the first part, but was mainly there to see if I had paid attention the first time. So, obviously there is 200 multiples of 5, 40 of 25, 8 of 125 and 1 of 625, so 149 trailing zeroes. However, I forgot to mention that there are no numbers in the range that are multiples of 55. The person doing it would count against me that I was told that I should include that final part, and so soon after failed to do so.
19. Just to make the above clearer, he means 100 FACTORIAL and 1000 FACTORIAL.
I was on a totally wrong tangent thinking 100?? Surely 2? then thinking oh, 1 to 100 inclusive silly me, surely thats 10,20...,90, 100, making 11 zeros, and then after 9000 more hours of puzzling, i figured it was factorial...
20. It appeared on step 1 2010 question 5 if anyone's interested

Reply
Submit reply
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 2, 2014
Today on TSR

Oxford interview invitations

When can you expect yours?

Official Cambridge interview invite list

Discussions on TSR

• Latest
• 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.

• Poll
Useful resources

Make your revision easier

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

How to use LaTex

Writing equations the easy way

Study habits of A* students

Top tips from students who have already aced their exams

Create your own Study Planner

Never miss a deadline again

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• 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.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.