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
Hello, taylor1234!
$\displaystyle \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: .$\displaystyle (1 + 2)^n$
consider the set $\displaystyle A$ of all functions $\displaystyle f: \{1,2, \cdots , n \} \longrightarrow \{a,b,c\}.$ clearly $\displaystyle |A|=3^n.$ now we'll find $\displaystyle |A|$ in a different way: for any $\displaystyle 0 \leq k \leq n$ let $\displaystyle A_k$ be the set of all $\displaystyle f \in A$ such that
$\displaystyle |f^{-1}\{a\}|=k.$ that means those $\displaystyle f \in A$ are in $\displaystyle A_k$ that map exactly $\displaystyle k$ elements of $\displaystyle \{1,2, \cdots , n \}$ to $\displaystyle a.$ there are $\displaystyle \binom{n}{k}$ ways to choose $\displaystyle k$ elements of a set with $\displaystyle n$ elements. also, for any
set $\displaystyle I \subseteq \{1,2, \cdots , n \}$ with $\displaystyle |I|=k$ there are $\displaystyle 2^{n-k}$ functions $\displaystyle f \in A$ with $\displaystyle f^{-1}\{a\} = I.$ therefore $\displaystyle |A_k|=\binom{n}{k}2^{n-k}.$ on the other hand, it is clear that $\displaystyle A_i \cap A_j = \emptyset$ for all $\displaystyle i \neq j$
and $\displaystyle A = \bigcup_{k=0}^n A_k.$ thus $\displaystyle |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.
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 $\displaystyle \sum_{k=0}^n |A(k)|$ = 3^n.
What is |A(k)|. It simply is $\displaystyle \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.