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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

Find a formula for: $$ \binom n0 + 2\binom n1 + 4\binom n2 + 8\binom n3 + \cdots + 2^{n-1}\binom n{n-1} + 2^n\binom nn $$ using a counting argument.

I just used the binomial t. to show it's $3^n$ but I can't find a combinatorial way. Any help?

share|cite|improve this question

marked as duplicate by user88595, amWhy, Najib Idrissi, Davide Giraudo, hardmath Jun 8 '14 at 13:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

up vote 10 down vote accepted

Consider counting functions $f: \{1,2,\dots,n\} \to \{1,2,3\}$ which we know there are $3^n$ of. The binomial coefficient $\binom{n}{i}$ chooses elements not to send to $3$ and the $2^i$ counts the ways to sending these elements into $\{1,2\}$. This defines a function just by sending everything not chosen to 3.

Best, John

share|cite|improve this answer
What a great argument! +1 :) – Alex Wertheim Jun 8 '14 at 3:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.