Take the 2-minute tour ×
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.

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

share|improve this question
3  
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
add comment

3 Answers

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

share|improve this answer
add comment

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$:

$$\sum_{k=0}n\binom{n}k2^k\;.$$

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|improve this answer
add comment

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 http://www.math.hmc.edu/calculus/tutorials/binomial_thm/combinatorial.pdf

share|improve this answer
add comment

Your Answer

 
discard

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.