-2
$\begingroup$

I am trying to show in the following equality that the left hand side equals the right hand side. I tried expanding out the summation but that didn't get me anywhere. Could somebody provide a hint? Thanks!

$\sum\limits_{k=0}^{n}\binom{n}{k}=(1+1)^n$

$\endgroup$

marked as duplicate by user147263, Did, Martin Sleziak, graydad, BruceET Sep 27 '15 at 21:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ See binomial expansion $$(a+b)^n$$ $\endgroup$ – lab bhattacharjee Sep 27 '15 at 13:57
  • $\begingroup$ Have you tried complete induction ? $\endgroup$ – callculus Sep 27 '15 at 14:01
  • $\begingroup$ What is your definition of $\binom{n}{k}$? It really helps to know if you have the computational or the combinatorial definition. $\endgroup$ – Thomas Andrews Sep 27 '15 at 14:04
  • $\begingroup$ You can find many posts about this here. For example, this question and this question and other posts linked there. $\endgroup$ – Martin Sleziak Sep 27 '15 at 20:36
1
$\begingroup$

We are having a party and we have a list of nn people who we may or may not invite. We ask, "how many different possibilities of guests are there?" One way to arrive to an answer is saying, "We can invite no one and there is exactly $n\choose 0$ ways to do that, or we can invite one person and there are $n\choose 1$ ways to do that, ect." Following this logic we arrive at the left hand side. However, we want to double check our answer so we try another method. We say, "We can associate each person with the number $0$ if they are not invited and $1$ if they are. Therefore, each possible configuration is represented by a string of $0$s and $1$s of length $n$. Since each slot in this string has $2$ possibilities, we find that there are exactly $2^n$ distinct strings." This agrees with the right hand side. Since both (valid) methods were used to find an answer to this problem, we see that the left and right sides of the equation must agree.

$\endgroup$
0
$\begingroup$

It may be easier to show $$\sum^n_{k=0} \binom{n}{k}x^{k}=(1+x)^n.$$ To see this, write $(1+x)^n$ as $$(1+x)^n=\underbrace{(1+x)(1+x)\cdots(1+x)}_n.$$ What is the coefficient of $x^k$ here -- We need to choose $k$ $x$'s out of the $n$ terms, therefore the coefficient is $\binom{n}{k}$.

$\endgroup$
  • $\begingroup$ Actually, the name binomial coefficient suggests that this equation is the "real" definition of $n\choose k$. $\endgroup$ – Hagen von Eitzen Sep 27 '15 at 14:04
0
$\begingroup$

Combinatory argument

How can you put $n$ ball in two boxes ? Of course, each ball has 2 possibilities, therefore, there is $2^n$ possibilities. But you can also put 0 ball in the box 1 and n in the box 2 with $\binom{n}{0}$ possibility, or 1 ball in the box 1 and n-1 in the box 2 with $\binom{n}{1}$ possibilities... finally you get $$\sum_{k=0}^n\binom{n}{k}$$ possibilies.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.