# Combinatorial sense of number of combinations

I have to prove that sum of all combinations $\left(^n_0\right) + \left(^n_1\right)+\left(^n_2\right)+...+\left(^n_n\right) = 2^n$, using combinatorial sense of number of combinations. So, i can't abuse the binomial theorem here. But what is the combinatorial sense of combinations?

I understand this sense as follows: $\left(^n_k\right)$ is the amount of ways how we can choose $k$ distinct elements from collection of $n$ distinct elements. So, then $\left(^n_0\right)$ is the amount of ways to choose $0$ elements. We can choose $0$ elements only by choosing nothing. There is only one way to choose nothing, so $\left(^n_0\right) = 1$. Then $\left(^n_1\right) = n$, $\left(^n_2\right) = \frac{n(n - 1)}{2}$. And this is the point, where i'm getting confused. Am i doing right things here? And if so, how can i accurately calculate my sum?

• Perhaps, it's best sticking to the exact combinatorial interpretation is $\binom nk$: the number of subsets with $k$ elements of a set of $n$ elements. – user228113 Oct 9 '16 at 22:47
• how many ways can you flip n coins? – Zackkenyon Oct 9 '16 at 22:47
• @Zackkenyon Yea, $2^n$. It is either $0$ or $1$. – False Promise Oct 9 '16 at 22:48
• how many ways can you flip n coins such that k of them are heads? – Zackkenyon Oct 9 '16 at 22:48
• @Zackkenyon Since, k elements are fixed, then $2^{n-k}$, not sure actually. – False Promise Oct 9 '16 at 22:51