Question

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

Answer 1

hey bb

Answer 2

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

Answer 3

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.

Answer 4

You can use binomial theorem.

Answer 5

As well as power set interpretation

Answer 6

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} \]



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}\]

Answer 7

induction over m

Answer 8

Binomial Theorem

Answer 9

\[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} \]