Let $n$ be a nonnegative integer. Prove that $\begin{align} 3^n = \sum_{k=0}^n \dbinom{n}{k} 2^k . \end{align}$
I know that $2^n = \sum\limits_{k=0}^n \dbinom{n}{k}$, but how to integrate the $2^k$ into this sum?
Let $n$ be a nonnegative integer. Prove that $\begin{align} 3^n = \sum_{k=0}^n \dbinom{n}{k} 2^k . \end{align}$
I know that $2^n = \sum\limits_{k=0}^n \dbinom{n}{k}$, but how to integrate the $2^k$ into this sum?
How do you derive $\sum_{k=0}^n{n \choose k}=2^n?$ For positive integer $n$
$\sum_{k=0}^n{n \choose k}x^k=(1+x)^n$
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$.
It is $\sum_{k=0}^n \binom{n}{k} 2^k \cdot 1^{n-k}=(1+2)^n$
Hint: $3^n=(2+1)^n{}{}{}{}{}$.
Let $A$ be the alphabet $\{a,b,c\}$. Let $W$ be the set of $n$-letter words over the alphabet $A$. There are $3^n$ words in $W$.
We count the words another way. For any $k$, where $0\le k\le n$, let $W_k$ be the set of $n$-letter words over $A$ that have exactly $k$ $c$'s. The location of the $c$'s can be chosen in $\binom{n}{k}$ ways. For any such choice, the rest of the locations can be filled with $a$'s and/or $b$'s in $2^k$ ways. Thus there are $\binom{n}{k}2^k$ words in $W_k$.
But $W$ is the disjoint union of the $W_k$. It follows that $3^n=\sum_{k=0}^n \binom{n}{k}2^k$.
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