Combinatorial argument with the binomial theorem: $\binom{n}{0} + \binom{n}{1} 2 + \binom{n}{2} 2^2 + ... + \binom{n}{n} {2^n}$

Question

For any positive integer n consider the expression $\dbinom{n}{0} + \dbinom{n}{1} 2 + \dbinom{n}{2} 2^2 + ... + \dbinom{n}{n} {2^n}$

Q) use the binomial theorem with appropriate values for x and y to simplify the expression. Now define a set of elements such that when you count the elements in two different ways you get each side of the identity.

Well i am assuming this means $x=y=1$ and that the sum equals $2^{n!} $ a counting argument for $2^{n!} $ (assuming that's what I'm doing) for $2^{n!} $ seems somewhat simple.

Consider how many different ways i can line up n people then ask them to select a red or blue jelly bean to eat. the other side just looks like gibberish to me.

Answer 1

Let A and B are two subsets of a set S of n elements. Find the number of tuples $(A,B)$ such that $ A \subset B \subset S$. The upper expression is this one. As choosing a B is choosing $\binom{n}{r}$ elements and then number of A's for that B is $2^r$ and summing over r gives the expression. The other way of counting this situation is that each element x has 3 choices:

a) $ x \in A,B,S$

b) $ x\in B,S ,\not \in A$

c) $ x \not \in A,B \in S$.

Thus the each element has 3 choices .So then total number of tuples is $3^n$. Also the binomal theorem gives the answer $ (1 +2)^n = 3^n$.