Mathematical Proof Problem! Oxbridge interview,

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?

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.

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.

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.

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

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.

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?

Posted from TSR Mobile

First, do you see why it is enough to show that the number of subsets of $\{1, 2, \dots, n \}$ is $2^n$?

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.

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?