Turn on thread page Beta
    • Thread Starter
    Offline

    16
    ReputationRep:
    Show that \displaystyle\sum^n_{m=0}\left({  \begin{array}{c}n\\ m\\

 \end{array}} \right) = 2^n

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

    \displaystyle\sum^n_{m=0}\left({  \begin{array}{c}n\\ m\\

 \end{array}} \right) = \left({\begin{array}{c}n\\ 0\\

 \end{array}} \right) + \left({\begin{array}{c}n\\ 1\\

 \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\

 \end{array}} \right) + \left({\begin{array}{c}n\\ n\\

 \end{array}} \right) = 1 + \left({\begin{array}{c}n\\ 1\\

 \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\

 \end{array}} \right) + 1 = 2 + 2 \left( \left({\begin{array}{c}n\\ 1\\

 \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 .
    Offline

    17
    ReputationRep:
    (Original post by ViralRiver)
    Show that \displaystyle\sum^n_{m=0}\left({  \begin{array}{c}n\\ m\\

 \end{array}} \right) = 2^n

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

    \displaystyle\sum^n_{m=0}\left({  \begin{array}{c}n\\ m\\

 \end{array}} \right) = \left({\begin{array}{c}n\\ 0\\

 \end{array}} \right) + \left({\begin{array}{c}n\\ 1\\

 \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\

 \end{array}} \right) + \left({\begin{array}{c}n\\ n\\

 \end{array}} \right) = 1 + \left({\begin{array}{c}n\\ 1\\

 \end{array}} \right) + ... + \left({\begin{array}{c}n\\ n-1\\

 \end{array}} \right) + 1 = 2 + 2 \left( \left({\begin{array}{c}n\\ 1\\

 \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 \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)
    • Thread Starter
    Offline

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

    17
    ReputationRep:
    (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.
    • Study Helper
    Online

    15
    Study Helper
    Regarding the original question.

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

    17
    ReputationRep:
    (Original post by ghostwalker)
    Regarding the original question.

    If you're allowed to assume the binomial expansion of (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.
    • Thread Starter
    Offline

    16
    ReputationRep:
    Not sure what you mean by that, ghostwalker?
    Offline

    9
    ReputationRep:
    (Original post by ViralRiver)
    Not sure what you mean by that, ghostwalker?
    The required expression is just the binomial expansion of (1+1)^n
    • PS Helper
    Offline

    14
    PS Helper
    (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 \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.
    Offline

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

    17
    ReputationRep:
    (Original post by nuodai)
    It's certainly not circular, since the binomial theorem doesn't rely on the result \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...)
    Offline

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

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

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

    14
    PS Helper
    (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?
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: September 27, 2011

University open days

  • Manchester Metropolitan University
    Postgraduate Open Day Postgraduate
    Wed, 14 Nov '18
  • University of Chester
    Chester campuses Undergraduate
    Wed, 14 Nov '18
  • Anglia Ruskin University
    Ambitious, driven, developing your career & employability? Aspiring in your field, up-skilling after a career break? Then our Postgrad Open Evening is for you. Postgraduate
    Wed, 14 Nov '18
Poll
Have you ever experienced bullying?
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

Equations

Best calculators for A level Maths

Tips on which model to get

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

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

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