## 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}$

1. Empty

hey bb

2. anonymous

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

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

You can use binomial theorem.

5. anonymous

As well as power set interpretation

6. ganeshie8

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

induction over m

8. UsukiDoll

Binomial Theorem

9. amoodarya

$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}$