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?

  • 1
    $\begingroup$ 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. $\endgroup$ – user228113 Oct 9 '16 at 22:47
  • $\begingroup$ how many ways can you flip n coins? $\endgroup$ – Zackkenyon Oct 9 '16 at 22:47
  • $\begingroup$ @Zackkenyon Yea, $2^n$. It is either $0$ or $1$. $\endgroup$ – False Promise Oct 9 '16 at 22:48
  • 1
    $\begingroup$ how many ways can you flip n coins such that k of them are heads? $\endgroup$ – Zackkenyon Oct 9 '16 at 22:48
  • $\begingroup$ @Zackkenyon Since, k elements are fixed, then $2^{n-k}$, not sure actually. $\endgroup$ – False Promise Oct 9 '16 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.