1 + (n choose 1)*2 + (n choose 2)*4 + . . . + (n choose n-1)*2^n-1 + (n choose n)*2^n = 3^n
Try to find a combinatorial proof
consider the set of all functions clearly now we'll find in a different way: for any let be the set of all such that
that means those are in that map exactly elements of to there are ways to choose elements of a set with elements. also, for any
set with there are functions with therefore on the other hand, it is clear that for all
and thus and the proof is complete.
To put whatever NonCommAlg said in a different way (a little non-abstract, I would say)
Consider 'n' different balls and 3 different urns. We can put the balls in these urns in 3^n ways. That makes the RHS of your equation.
Now consider another way to count the same.
Let A(k) = Number of ways to put 'k' balls in first two urns and rest in 3rd urn. k ranges from 0 to n.
A(k) form mutually exclusive and exhaustive events. Hence = 3^n.
What is |A(k)|. It simply is . Select k balls first and then put k balls in 2 urns.
Hence the result.
Please Note: My definition ok A(k), though similar in construct, is not equaly to how NonCommAlg defined it.