Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The sum of all the different ways to multiply together $a,b,c,d,\ldots$ is equal to $$(a+1)(b+1)(c+1)(d+1)\cdots$$ right?

If this is true? why is it true?

share|improve this question
    
You might have a look at Elementary Symmetric Polynomials... –  draks ... Dec 16 '12 at 22:24
add comment

2 Answers

up vote 3 down vote accepted

If I understand correctly, you’re asking about the following result.

Let $A$ be a finite set of real numbers. Then $$\sum_{S\subseteq A}\prod S=\prod_{a\in A}(a+1)\;.\tag{1}$$

For instance, if $A=\{a,b,c\}$, then the subsets and their products are:

$$\begin{array}{c} \text{Subset}&\text{Product}\\ \hline \varnothing&1\\ \{a\}&a\\ \{b\}&b\\ \{c\}&c\\ \{a,b\}&ab\\ \{a,c\}&ac\\ \{b,c\}&bc\\ \{a,b,c\}&abc \end{array}$$

And the sum is $$abc+ab+ac+bc+a+b+c+1=(a+1)(b+1)(c+1)\;.$$

To see why this works, let $A=\{a_1,\dots,a_n\}$, and consider the product $\prod_{k=1}^n(a_k+1)$. This is a product of $n$ binomials, so it has $2^n$ terms when you multiply it out fully. In the example above, for instance, you get

$$a\cdot b\cdot c+a\cdot b\cdot1+a\cdot1\cdot c+1\cdot b\cdot c+a\cdot 1\cdot 1+1\cdot b\cdot 1+1\cdot 1\cdot c+1\cdot 1\cdot 1\;.$$

Each term $t$ is a product of $n$ factors, one from each of the $n$ binomials. Thus, a typical term has the form $t=x_1x_2\dots x_n$, where each $x_k$ is either $a_k$ or $1$. Let $S_t=\{a_k:x_k=a_k\}$; then $t=\prod S_t$, since the other factors in the term $t$ are all $1$. Each term of the product is therefore of the form $\prod S$ for some $S\subseteq A$, and it’s not hard to see that each $S\subseteq A$ gives rise to a term in the product $\prod_{k=1}^n(a_k+1)$.

In other words, when you multiply out the righthand side of $(1)$, you get precisely the lefthand side: each term of the muliplied-out product is one of the terms $\prod S$ for $S\subseteq A$, and each $S\subseteq A$ gives rise to one of the terms in ther product on the righthand side of $(1)$.

share|improve this answer
add comment

Yes it is true, give it a try...

Ok, sorry. Here's a little more detail:

We have the identity $$ \prod_{j=1}^n ( \lambda-X_j)=\lambda^n-e_1(X_1,\ldots,X_n)\lambda^{n-1}+e_2(X_1,\ldots,X_n)\lambda^{n-2}-\cdots+(-1)^n e_n(X_1,\ldots,X_n). $$ $\biggr[$use $\lambda=-1$ to get $ \prod_{j=1}^n ( -1-X_j)=(-1)^n\prod_{j=1}^n ( 1+X_j)$$\biggr]$

This can be proven by a double mathematical induction with respect to the number of variables n and, for fixed n, with respect to the degree of the homogeneous polynomial.

I really thought that giving it a try would show some inside.

Hope the links help,

share|improve this answer
    
I don't think "give it a try" suffices for justification of why the statement is true. I won't downvote this answer, because it isn't wrong, per se, but I think you ought to give more detail, or simply change it to a comment. –  Cameron Buie Dec 16 '12 at 21:04
    
@CameronBuie you're right. Have a look... –  draks ... Dec 16 '12 at 22:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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