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?

DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 1
 30062014 22:32

Smaug123
 Follow
 23 followers
 13 badges
 Send a private message to Smaug123
 PS Helper
 Study Helper
Offline13ReputationRep: Follow
 2
 30062014 22:39
(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?
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.Last edited by Smaug123; 30062014 at 22:41. Reason: ETA 
 Follow
 3
 30062014 22:57
(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? 
Smaug123
 Follow
 23 followers
 13 badges
 Send a private message to Smaug123
 PS Helper
 Study Helper
Offline13ReputationRep: Follow
 4
 30062014 23:12
(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. 
DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 5
 30062014 23:46
(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.
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?Last edited by DomStaff; 01072014 at 00:22. Reason: Extra thought. 
 Follow
 6
 30062014 23:51
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. 
DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 7
 01072014 00:06
(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. 
DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 8
 01072014 00:08
(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. 
 Follow
 9
 01072014 00:24
(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.).
EDIT: The induction method is more difficult than I first realised. It will still work, but you should go for the other methods instead.Last edited by james22; 01072014 at 00:26. 
Smaug123
 Follow
 23 followers
 13 badges
 Send a private message to Smaug123
 PS Helper
 Study Helper
Offline13ReputationRep: Follow
 10
 01072014 09:28
(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. 
 Follow
 11
 01072014 09:48
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 
Jammy Duel
 Follow
 48 followers
 21 badges
 Send a private message to Jammy Duel
 Political Ambassador
Online21ReputationRep: Follow
 12
 01072014 09:52
(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
EDIT: MB, didn't see that this was the first post of page 2 and not OP.
Posted from TSR MobileLast edited by Jammy Duel; 01072014 at 12:20. 
davros
 Follow
 39 followers
 16 badges
 Send a private message to davros
 Study Helper
Offline16ReputationRep: Follow
 13
 01072014 10:11
(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
Personally I think there's a bit of "overthinking" 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! 
DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 14
 01072014 10:19
(Original post by Smaug123)
First, do you see why it is enough to show that the number of subsets of is ?
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.Last edited by DomStaff; 01072014 at 10:32. 
DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 15
 01072014 10:23
(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 "overthinking" 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! 
Jammy Duel
 Follow
 48 followers
 21 badges
 Send a private message to Jammy Duel
 Political Ambassador
Online21ReputationRep: Follow
 16
 01072014 10:55
(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.
Posted from TSR Mobile 
DomStaff
 Follow
 26 followers
 2 badges
 Send a private message to DomStaff
 Thread Starter
Offline2ReputationRep: Follow
 17
 01072014 11:54
(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 
Jammy Duel
 Follow
 48 followers
 21 badges
 Send a private message to Jammy Duel
 Political Ambassador
Online21ReputationRep: Follow
 18
 01072014 12:38
(Original post by DomStaff)
Yes would you please post an example?
So, in a practice interview I was asked something along the lines of "How many trailing, nondecimal, zeros are there are on 100!?"Spoiler:ShowWith 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, nondecimal, zeroes in 1000! ?"Spoiler:ShowSo, 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 5^{5}. 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. 
 Follow
 19
 01072014 17:14
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...Last edited by Tasaber; 01072014 at 17:22. 
 Follow
 20
 01072014 18:47
It appeared on step 1 2010 question 5 if anyone's interested
Reply
Submit reply
Related discussions:
 The Proof is Trivial!
 Extra university appliction for Oxbridge
 Official TSR Mathematical Society
 I went to a state school
 Do you regret going to Cambridge University?
 Oxford Rejection
 Anyone else lost faith in the "decision based solely on ...
 Rejected by Oxford despite IB 45, don't know what to think ...
 Oxbridge warning
 Official Cambridge 2018 Interview Invitations
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:
 SherlockHolmes
 Notnek
 charco
 Mr M
 TSR Moderator
 Nirgilis
 usycool1
 Changing Skies
 James A
 rayquaza17
 RDKGames
 randdom
 davros
 Gingerbread101
 Kvothe the Arcane
 The Financier
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Leviathan1741
 Moltenmo
Updated: July 2, 2014
Share this discussion:
Tweet