# How to simplify a sum of combinatorial values into a single value?

Edit: I've tried to make this question more clear.

I know how algebra and calculus work, and can solve problems like these, where the point of the problem is to just simplify a term into its simplest form:

$$\dfrac{x^4 + x^4}{x^5} = \dfrac{2x^4}{x^5} = \dfrac{2}{x}$$

$$\int_0^y 2x = x^2 \bigr\rvert_0^y = y^2 - 0^2 = y^2$$

As in, I know what the middle steps are to get from the left-most side of the equation to the right-most side of the equation. But, I don't know what the middle steps of this equation are:

$$\sum_{r=0}^n \dfrac{n!}{r!(n-r)!} =\mathbf?=2^n$$

If this was a question on a test and I had to show my work, what would the middle steps be for this equation? Is there a way to solve it like you could solve the algebra and calculus problems above? I really hope this isn't a dumb question, but I just want to know and haven't been able to figure it out myself.

• For each of $n$ ingredients, you have two choices: include it or don't. That gives $2^n$ recipes. Apr 27 '18 at 1:18
• Hint: $2^n$ is always even. 3 from 7 = 35. Apr 27 '18 at 1:27
• I guess I asked the question a little too vaguely. If someone gave me the left hand side of the bottom equation, what are the steps you'd need to do to simplify it into the right hand side? Apr 27 '18 at 19:17

Well, the algebraic way I know to prove the statement you have given is by the binomial theorem; just expand out $(1+1)^n$ (Binomial theorem in spirit is still combinatorial though).

Intuitively though, one of them sums up the number of ways you can choose $r$ ingredients out of a list of $n$ things, and you sum over all $r$; that just gives you the number of subsets you could have, since you essentially include all possible subsets this way.

• Sorry, I don't understand what you mean by expanding the Binomial theorem to algebraically solve the equation. If someone gave me only the left hand side of the bottom equation with no context, how would you turn it into the right hand side? Apr 27 '18 at 19:18
• Do you know how to expand $(a+b)^2$? How about $(a+b)^n?$
– E-A
May 7 '18 at 2:21
• I can expand $(a+b)^2$, and could theoretically expand $(a+b)^n$ if I had enough time. How do you get from $\sum_{r=0}^n\frac{n!}{r!(n-r)!}$ to $(1+1)^n$? May 7 '18 at 20:29
• Ok, so if you expand $(a+b)^n$, you get $\sum_{r=0}^n \binom{n}{r} a^r b^{n-r} = \sum_{r=0}^n \frac{n!}{r!(n-r)!} a^r b^{n-r}$. Now plug in $a=1, b=1$.
– E-A
May 9 '18 at 20:46
• Oooohhh, I see. So if you know that the binomial theorem is $(a+b)^n = \sum_{r=0}^n \frac{n!}{r!(n-r)!}a^rb^{n-r}$, then you could express the problem $\sum_{r=0}^n \frac{n!}{r!(n-r)!}$ as $\sum_{r=0}^n \frac{n!}{r!(n-r)!}(1)^r(1)^{n-r}$, and then substituting for $a$ and $b$ in $(a+b)^n$ you get $(1 + 1)^n = 2^n$. This is what I was looking for! Thank you! May 10 '18 at 0:54

Think of this as a set, such as $\{\text{pork, cabbage, shrimp}\}$. For each ingredient, you can choose whether to include or not to include it. Therefore for $x$ ingredients, you have $2^x$ ways of making dumplings with those ingredients.