# Combinatorial proof help

I have to prove the identity using a combinatorial proof:

$\displaystyle\sum\limits_{k=0}^n 2^k \binom{n}{k} = 3^n$

I think this should be my combinatorial proof:

We want to form a committee of $k$ people from a total of $n$ people. There are two ways of counting this committee.

1) Go through each member from the $n$ total people, and decide if they should be added to the committee or not, until we have reached $k$ people. This gives us the LHS.

...For the RHS, however, I am not sure how to form it. I think it should be something like forming subsets of $3$ people and choosing from that, but I'm not sure how that will form the same committee as the LHS.

EDIT: Okay, I also had the idea of forming a ternary string, and I could get the RHS this way. But I was not sure about the LHS. But the first answer gave me the right idea. Thanks a lot.

-
While calculating k people committee from n people committee you will get $\binom{\displaystyle n}{\displaystyle k}$ but how would you account for $2^{k}$ on the LHS ?? –  Ramana Venkata Oct 2 '11 at 17:06
If this is a homework problem, it should carry the homework tag. If not, please ignore :-) –  robjohn Oct 2 '11 at 17:13
@Ramana True, agreed. Yeh, I should use a ternary string idea. –  user952949 Oct 2 '11 at 17:13
@robjohn: Ok, tagged :) –  user952949 Oct 2 '11 at 17:58

We want to form $n$-letter words over the alphabet $\{a,b,c\}$. There are $3^n$ such words.

To count these words in another way, take a fixed $k$, where $0 \le k \le n$. To make an $n$-letter word with a total of $k$ $a$'s and/or $b$'s, choose the $k$ positions that will have $a$ and/or $b$. This can be done in $\binom{n}{k}$ ways. For each such way, these $k$ positions can be filled with $a$'s and/or $b$'s in $2^k$ ways, for a total of $2^k \binom{n}{k}$ ways. For each of these $2^k\binom{n}{k}$ ways, there is only one way to put in the $c$'s. Finally, add up, $k=0$ to $n$.

-
Thanks. I was also thinking of using a ternary string idea at first. I could form the RHS, but was having trouble with the LHS. Thanks for the pointer, this helps. –  user952949 Oct 2 '11 at 17:18
If you are going to tell two stories, one for the right, one for the left, committees ("choose") seem unsuitable. You can easily generalize the above idea in various ways, to get other identities. –  André Nicolas Oct 2 '11 at 17:46

There is a nice double counting proof, from the geometric point of view. Consider all faces of a n-cube. These faces can be encoded by a sequence of "0", "1" and a "*", where the star signifies that the coordinate can be either 0 or 1 in the face. This immediately gives $3^n$ faces. On the other hand, the number of $k$-dimensional faces is equal to $\binom{n}{k}$ way of choosing $k$ coordinates times $2^{n-k}$ ways of fixing the remaining coordinates, all summed over all $k=1..n$. Of course, this proof is actually equivalent to that by Andre above.

P.S. This is actually Example 8.3 in my discrete geometry book (sorry for the shameless plug - much of the book is about something else).

-
Thanks for the reference :). –  Srivatsan Oct 6 '11 at 3:09
Wow, thanks for pointing me to a geometry proof. Very interesting :D –  user952949 Oct 6 '11 at 19:00

While you are not looking for an algebraic proof, the algebraic proof using the binomial theory is tempting...

$\sum_{k=0}^{n} \binom{n}{k} (1+1)^{k}.1^k=(2+1)^n$

-
But we have to prove it using double counting. But yes, an algebraic proof would look nice and neat. –  user952949 Oct 6 '11 at 18:58
Hint: Remember that $3^n$ is the number of ways to put a set of $n$ distinct things into an array of $3$ containers. Likewise, $2^n$ is the number of ways to put a set of $n$ distinct things into an array of $2$ containers.
@user952949: Since it's been 4 days, there's probably no harm in mentioning that there are $\binom{n}{k}$ ways to choose which $k$ things go into the first two containers and which $n-k$ things go into the third. –  robjohn Oct 6 '11 at 17:56