The Student Room Group

Binomial Question (Show that)

Show that
Unparseable latex formula:

\displaystyle\sum^n_{m=0}\left({\begin{array}{c}n\\ m\\[br] \end{array}} \right) = 2^n



Right, here's my working out so far, not sure what to do from here though:

Unparseable latex formula:

\displaystyle\sum^n_{m=0}\left({\begin{array}{c}n\\ m\\[br] \end{array}} \right) = \left({\begin{array}{c}n\\ 0\\[br] \end{array}} \right) + \left({\begin{array}{c}n\\ 1\\[br] \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\[br] \end{array}} \right) + \left({\begin{array}{c}n\\ n\\[br] \end{array}} \right)

Unparseable latex formula:

= 1 + \left({\begin{array}{c}n\\ 1\\[br] \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\[br] \end{array}} \right) + 1 = 2 + 2 \left( \left({\begin{array}{c}n\\ 1\\[br] \end{array}} \right) + ... \right)



Not really sure of the correct syntax for that last step I typed out, but that's basically as far as I can get. I can see a pattern obviously involving 2s, but that's about it :P .
(edited 12 years ago)
Original post by ViralRiver
Show that
Unparseable latex formula:

\displaystyle\sum^n_{m=0}\left({\begin{array}{c}n\\ m\\[br] \end{array}} \right) = 2^n



Right, here's my working out so far, not sure what to do from here though:

Unparseable latex formula:

\displaystyle\sum^n_{m=0}\left({\begin{array}{c}n\\ m\\[br] \end{array}} \right) = \left({\begin{array}{c}n\\ 0\\[br] \end{array}} \right) + \left({\begin{array}{c}n\\ 1\\[br] \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\[br] \end{array}} \right) + \left({\begin{array}{c}n\\ n\\[br] \end{array}} \right)

Unparseable latex formula:

= 1 + \left({\begin{array}{c}n\\ 1\\[br] \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\[br] \end{array}} \right) + 1 = 2 + 2 \left( \left({\begin{array}{c}n\\ 1\\[br] \end{array}} \right) + ... \right)



Not really sure of the correct syntax for that last step I typed out, but that's basically as far as I can get. I can see a pattern obviously involving 2s, but that's about it :P .

Induction.

You may want to use the result (x−1r−1)+(x−1r)=(xr)\begin{pmatrix} x-1 \\ r-1 \end{pmatrix} + \begin{pmatrix} x-1 \\ r \end{pmatrix} = \begin{pmatrix} x \\ r \end{pmatrix} (which is easily shown)
Reply 2
Thanks, one other question. How can you expand work out 1.005^7 to 3dp without a calculator? I've expanded it as (1+0.005)^7 but still seems a bit hard mentally.
Original post by ViralRiver
Thanks, one other question. How can you expand work out 1.005^7 to 3dp without a calculator? I've expanded it as (1+0.005)^7 but still seems a bit hard mentally.


That seems like the neatest way to do it. Notice that you only need to expand up to the term involving 0.005^3 as the other terms won't affect the 3rd decimal place.
Regarding the original question.

If you're allowed to assume the binomial expansion of (x+y)n(x+y)^n, then just set x=y=1.
Original post by ghostwalker
Regarding the original question.

If you're allowed to assume the binomial expansion of (x+y)n(x+y)^n, then just set x=y=1.

I thought this but I expected it would make the problem a little too trivial? Felt a little circular.
Reply 6
Not sure what you mean by that, ghostwalker?
Original post by ViralRiver
Not sure what you mean by that, ghostwalker?


The required expression is just the binomial expansion of (1+1)n(1+1)^n
Reply 8
Original post by Farhan.Hanif93
I thought this but I expected it would make the problem a little too trivial? Felt a little circular.


It's certainly not circular, since the binomial theorem doesn't rely on the result ∑0n(nm)=2n\sum_0^n \binom{n}{m} = 2^n; and (like many things) it only makes the problem trivial if you spot the trick. Induction's always a safe approach, but the binomial theorem's a much more illustrative approach.
Reply 9
Binomial coefficients count stuff right? So we'd like to interpret that sum as counting something.

Remember that nCm is the number of ways to choose m elements from a set of n, so if we sum over m we are effectively saying 'how many subsets of a set of size n are there' (because we add the number of sets of size 0, the number of sets of size 1, etc etc).

We can also think about specifying the elements of a subset by lining up the elements of the set of size n and then either writing 1 or 0 underneath each element, to show whether they're in our subset of not. So it should be pretty clear that each element can either be or not be in our set, and hence there are 2^n subsets.
Original post by nuodai
It's certainly not circular, since the binomial theorem doesn't rely on the result ∑0n(nm)=2n\sum_0^n \binom{n}{m} = 2^n; and (like many things) it only makes the problem trivial if you spot the trick. Induction's always a safe approach, but the binomial theorem's a much more illustrative approach.

I don't think I've used the correct word to describe what I meant here but surely you can't just assume the theorem when the proposition is just a special case of that very theorem? (I may be over complicating things...)
STEP I 2010? Nice paper.


Original post by around
Binomial coefficients count stuff right? So we'd like to interpret that sum as counting something.

Remember that nCm is the number of ways to choose m elements from a set of n, so if we sum over m we are effectively saying 'how many subsets of a set of size n are there' (because we add the number of sets of size 0, the number of sets of size 1, etc etc).

We can also think about specifying the elements of a subset by lining up the elements of the set of size n and then either writing 1 or 0 underneath each element, to show whether they're in our subset of not. So it should be pretty clear that each element can either be or not be in our set, and hence there are 2^n subsets.

Very nice, I was thinking about the power set thing but your whole binary tree thing was a beautiful touch. +repped.
Original post by Farhan.Hanif93
I don't think I've used the correct word to describe what I meant here but surely you can't just assume the theorem when the proposition is just a special case of that very theorem? (I may be over complicating things...)
There's a certain logic to what you say, but unless you're told otherwise, I think you're pretty safe assuming the binomial theorem in a question.
Original post by DFranklin
There's a certain logic to what you say, but unless you're told otherwise, I think you're pretty safe assuming the binomial theorem in a question.


It is in the formula booklet, after all.
Reply 14
Original post by Farhan.Hanif93
I don't think I've used the correct word to describe what I meant here but surely you can't just assume the theorem when the proposition is just a special case of that very theorem? (I may be over complicating things...)


I can see where you're coming from, but it's a consequence of the theorem. Why prove theorems if not to explore their consequences?

Quick Reply

Latest