How can I compute $\sum\limits_{k = 1}^n \binom{n - 1}{k - 1}$?

Question

I know what $n \choose k$ equals, but I don't see how that would help me solve the sum of $n - 1 \choose k - 1$ from $k = 1$ to $n$. Is there any special trick I should know?

Answer 1

Here's a combinatorial way to approach the problem if you understand what the binomial coefficient ${{n-1} \choose {k-1}}$ means. It's the number of ways you can choose a (unordered) subset of size $k-1$ from a (unordered) set of $n-1$ elements. So if your sum is from $k=1$ to $k = n$, then you are adding up all the ways you can choose an arbitrary unordered subset of any size, from 0 up to $n-1$. This is $2^{n-1}$, because for each of the $n-1$ elements in your set, you have two choices: Either the element is in the subset or not.

Answer 2

Hint: Binomial Expansion of $(1+1)^{n-1} = \sum_{k=1}^{n-1}{n-1 \choose k-1}1^k1^{n-k}$ will lead to the sum you have asked for.

Answer 3

Change the index by setting $j = k - 1$. Then $$\sum_{k = 1}^n \binom{n-1}{k-1} = \sum_{j = 0}^{n-1}\binom{n-1}{j} = (1 + 1)^{n-1} = 2^{n-1}.$$