Hey there! Sign in to join this conversationNew here? Join for free

Mathematical Proof Problem! Oxbridge interview, Watch

    • Thread Starter
    Offline

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

    \sum_{r=0}^n \displaystyle \binom{n}{r} = 2^n

    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

    (a+b)^n = \sum_{r=0}^n \displaystyle \binom{n}{r} a^n b^{n-k}

    and setting a=b=1, prove this?
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    (Original post by DomStaff)
    This is something you are asked to prove from a set of sample questions for a mathematics interview at Downing.

    \sum_{r=0}^n \displaystyle \binom{n}{r} = 2^n

    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

    (a+b)^n = \sum_{r=0}^n \displaystyle \binom{n}{r} a^n b^{n-k}

    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: \binom{n}{r} is the number of subsets of \{1, 2, \dots, n \} of size r. Hence the sum \sum_{r=0}^n \displaystyle \binom{n}{r} is just the number of subsets of \{1, 2, \dots, n \}. 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.
    Offline

    11
    ReputationRep:
    (Original post by Smaug123)
    The easiest way to see it is: \binom{n}{r} is the number of subsets of \{1, 2, \dots, n \} of size r. Hence the sum \sum_{r=0}^n \displaystyle \binom{n}{r} is just the number of subsets of \{1, 2, \dots, n \}. 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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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: \binom{n}{r} is the number of subsets of \{1, 2, \dots, n \} of size r. Hence the sum \sum_{r=0}^n \displaystyle \binom{n}{r} is just the number of subsets of \{1, 2, \dots, n \}. 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?
    Offline

    15
    ReputationRep:
    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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.).
    Offline

    15
    ReputationRep:
    (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.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    (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 \{1, 2, \dots, n \} is 2^n?
    Offline

    10
    ReputationRep:
    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
    • Political Ambassador
    Online

    21
    ReputationRep:
    (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
    • Study Helper
    Offline

    16
    ReputationRep:
    (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!
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by Smaug123)
    First, do you see why it is enough to show that the number of subsets of \{1, 2, \dots, n \} is 2^n?
    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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
    • Political Ambassador
    Online

    21
    ReputationRep:
    (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
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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?
    • Political Ambassador
    Online

    21
    ReputationRep:
    (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.
    Offline

    0
    ReputationRep:
    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...
    Offline

    10
    ReputationRep:
    It appeared on step 1 2010 question 5 if anyone's interested
 
 
 
  • 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
    What newspaper do you read/prefer?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

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

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