Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

How would I prove that $3^n = \sum_{k=0}^n \binom {n} {k} 2^k$ for any positive integer $n$?

share|cite|improve this question
Do you know the binomial theorem? – Ayman Hourieh Sep 24 '12 at 8:35
Hint: let $\:2 = x,\:$ so $\rm\:3 = 1+x.\:$ Recognize the famous theorem now? – Bill Dubuque Sep 24 '12 at 15:50

Hint: $3^n=(2+1)^n{}{}{}{}{}$.

share|cite|improve this answer

If you don’t know the binomial theorem, you can still prove it using a combinatorial argument.

$3^n$ is the number of $n$-letter strings that you can make using only $a$’s, $b$’s, and $c$’s; that counts them all at once, but we can count them in another way as well. One way to form such a string is to pick first which positions in the string won’t be $a$’s. If we decide to have $k$ letters that aren’t $a$’s, there are $\binom{n}k$ ways to decide where to put them; the other $n-k$ letters will of course be $a$’s. Then for each of those $k$ positions that won’t be occupied by $a$’s, we have to decide whether to put a $b$ or a $c$ there. That’s a two-way choice, and we have to make $k$ such choices independently, so there are $2^k$ ways to make these choices. Thus, there are altogether $\binom{n}k2^k$ strings that have a total of $k$ $b$’s and $c$’s. To get the total number of strings, just add up these numbers $\binom{n}k2^k$ for all possible values of $k$, i.e., for $k=0$ to $k=n$:


Since this is just another way of counting the $n$-letter strings containing nothing but $a$’s, $b$’s, and $c$’s, it must be $3^n$.

share|cite|improve this answer

Using Binomial Theorem, $(1+x)^n=\sum_{k=0}^{n}{n\choose k}x^k$

Putting $x=2$ gives you your answer.

See combinatorial proof of binomial theorem

share|cite|improve this answer

Your Answer


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.