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.

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.

share|improve this question
    
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
add comment

4 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
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
add comment

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).

share|improve this answer
    
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
add comment

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$

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Yes, true. I was thinking about it in a stupid way, I should use a forming a string method, much more intuitive than the committee method. –  user952949 Oct 2 '11 at 17:19
    
@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
    
Thanks for your help :) I finished the proof a while ago, I forgot to close the question. –  user952949 Oct 6 '11 at 18:57
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.