1. ## Combinatorial Proof

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

2. Hello, taylor1234!

$\text{Prove that: }\;1 + {n\choose1}\cdot2 + {n\choose2}\cdot2^2 + {n\choose3}\cdot2^3 + \hdots + {n\choose n}\cdot2^n \;=\; 3^n$

This probably doesn't qualify as a "combinatorial proof", but . . .

. . Note that the left side of the equation is: . $(1 + 2)^n$

3. consider the set $A$ of all functions $f: \{1,2, \cdots , n \} \longrightarrow \{a,b,c\}.$ clearly $|A|=3^n.$ now we'll find $|A|$ in a different way: for any $0 \leq k \leq n$ let $A_k$ be the set of all $f \in A$ such that

$|f^{-1}\{a\}|=k.$ that means those $f \in A$ are in $A_k$ that map exactly $k$ elements of $\{1,2, \cdots , n \}$ to $a.$ there are $\binom{n}{k}$ ways to choose $k$ elements of a set with $n$ elements. also, for any

set $I \subseteq \{1,2, \cdots , n \}$ with $|I|=k$ there are $2^{n-k}$ functions $f \in A$ with $f^{-1}\{a\} = I.$ therefore $|A_k|=\binom{n}{k}2^{n-k}.$ on the other hand, it is clear that $A_i \cap A_j = \emptyset$ for all $i \neq j$

and $A = \bigcup_{k=0}^n A_k.$ thus $|A|=\sum_{k=0}^n |A_k|= \sum_{k=0}^n \binom{n}{k}2^{n-k}=\sum_{k=0}^n \binom{n}{k}2^k$ and the proof is complete.

4. 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 $\sum_{k=0}^n |A(k)|$ = 3^n.

What is |A(k)|. It simply is $\binom{n}{k}2^k$. 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.