A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

dan815

  • one year ago

just for fun, see if you think of some ways to prove \[\sum_{k=0}^{m-1}\binom{m-1}{k}=2^{m-1}\]

  • This Question is Closed
  1. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    hey bb

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    A combinatoric interpretation of this fact is given by counting subsets of different sizes of a set \(S\) of \(m-1\) elements. Since we count the number of subsets of size \(k\) for \(0 \le k \le m-1\), this sum must be equal to the number of subsets of \(S\), which is \(2^{m-1}\).

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Consider \(m-1\) place for a subset. For each subset it can either include or not include an element. For each element, there are \(2\) possibilities. Multiplying these together we get \(2^{m-1}\) subsets.

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    You can use binomial theorem.

  5. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    As well as power set interpretation

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Just for the sake of alternative, using pascal's rule can be enlightening too \[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} \] |dw:1435740725845:dw| Induction step goes like this \[\begin{align} \sum\binom{m}{k}&=\sum\left[\binom{m-1}{k-1}+\binom{m-1}{k}\right]\\~\\ &=\sum\binom{m-1}{k-1}+\sum\binom{m-1}{k}\\~\\&=2^{m-1}+2^{m-1}\\~\\&=2^{m} \end{align}\]

  7. amoodarya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    induction over m

  8. UsukiDoll
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Binomial Theorem

  9. amoodarya
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[A=\left\{ a_1,a_2,a_3,...,a_{m-1} \right\}\\card(a)=m-1\\ \left(\begin{matrix}m-1 \\ 0\end{matrix}\right)+\left(\begin{matrix}m-1 \\ 1\end{matrix}\right)+...+\left(\begin{matrix}m-1 \\ m-1\end{matrix}\right)=total \space \space subsets \space of A\\=2^{card(A)}=2^{m-1} \]

  10. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.